結果
問題 |
No.54 Happy Hallowe'en
|
ユーザー |
![]() |
提出日時 | 2024-07-30 13:10:24 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,102 bytes |
コンパイル時間 | 1,363 ms |
コンパイル使用メモリ | 115,040 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-07-30 13:10:27 |
合計ジャッジ時間 | 3,006 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 9 WA * 10 |
ソースコード
#include<iostream> #include<vector> #include<algorithm> using namespace std; using ll = long long; #include<set> int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n; cin>>n; vector<ll> v(n),t(n); for(int i = 0;i<n;i++) cin>>v[i]>>t[i]; ll sum = 0; for(int i = 0;i<n;i++) sum += v[i]; ll right = sum + 1; ll left = 0; vector<int> idx(n); for(int i = 0;i<n;i++) idx[i] = i; sort(idx.begin(),idx.end(),[&](int i,int j){ return t[i] + v[i] - 1 > t[j] + v[j] - 1; }); auto calc = [&](ll now) { set<ll> all; all.insert(now); for(int i = 0;i<n;i++){ int ni = idx[i]; auto itr = all.upper_bound(t[ni]+v[ni]-1); if(itr!=all.begin()){ itr--; ll use = *itr; if(t[ni]+v[ni]-1>=use) all.insert(use-v[ni]); } } return all.count(0); }; while(right-left>1){ ll mid = (right+left) / 2; if(calc(mid)) left = mid; else right = mid; } cout<<left<<endl; }