結果
問題 | No.817 Coin donation |
ユーザー |
![]() |
提出日時 | 2019-04-22 10:20:43 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 85 ms / 2,000 ms |
コード長 | 814 bytes |
コンパイル時間 | 1,712 ms |
コンパイル使用メモリ | 170,432 KB |
実行使用メモリ | 11,720 KB |
最終ジャッジ日時 | 2024-10-09 19:46:57 |
合計ジャッジ時間 | 2,908 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 14 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<ll> vl; typedef long double ld; typedef vector<ld> vd; typedef bool bl; typedef vector<bl> vb; typedef unordered_map<ll,unordered_map<ll,ll>> graph; const ll e5 = 1 << 20; const ll mod = 998244353; const ll e3 = 1 << 13; const ll INF = 1ll << 60; ll n,k; ll a[e5],b[e5]; map<ll,ll> m; ll dp[e5]; ll ans; int main(){ cin >> n >> k; for(ll i = 0;i < n;i++) cin >> a[i] >> b[i]; ll top = 1000000000; ll bottom = 0; while(top-bottom > 1){ ll middle = (top+bottom)/2; ll mem = 0; for(ll i = 0;i < n;i++){ if(a[i] > middle) continue; if(b[i] > middle) mem += middle-a[i]+1; else mem += b[i]-a[i]+1; } if(mem >= k) top = middle; else bottom = middle; } cout << top << endl; }