結果
問題 | No.817 Coin donation |
ユーザー |
![]() |
提出日時 | 2020-02-09 04:29:29 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 139 ms / 2,000 ms |
コード長 | 1,262 bytes |
コンパイル時間 | 2,655 ms |
コンパイル使用メモリ | 196,396 KB |
最終ジャッジ日時 | 2025-01-08 23:17:18 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 14 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using PII = std::pair<int, int>; using PLL = std::pair<ll, ll>; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define rep2(i, s, n) for (int i = (s); i < (int)(n); i++) vector<vector<int>> donates; ll coin(int k) { ll a, b, n, l, m, r; l = m = r = 0; n = donates.size(); rep(i, n) { a = donates[i][0], b = donates[i][1]; if (a <= k && k <= b) { l += k - a; m += 1; r += b - k; } else if (b < k) l += b - a + 1; else if (a > k) r += b - a + 1; } return l+1; } int main() { #ifdef DEBUG cout << "DEBUG MODE" << endl; ifstream in("input.txt"); //for debug cin.rdbuf(in.rdbuf()); //for debug #endif int n, k, x; ll ok, ng, mid; cin >> n >> k; donates.resize(n); rep(i, n) { rep(j, 2) { cin >> x; donates[i].push_back(x); } } coin(0); ok = 1e9+1, ng = 0; while (ok - ng > 1) { mid = (ok + ng) / 2; if (coin(mid) > k) ok = mid; else ng = mid; } cout << ng << endl; return 0; }