Submission #334245

#TimeUsernameProblemLanguageResultExecution timeMemory
334245limabeansDivide and conquer (IZhO14_divide)C++17
0 / 100
2 ms492 KiB
#include <bits/stdc++.h> using namespace std; template<typename T> void out(T x) { cout << x << endl; exit(0); } #define watch(x) cout << (#x) << " is " << (x) << endl using ll = long long; const int maxn = 1e6 + 5; int n; ll x[maxn], g[maxn], d[maxn]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n; for (int i=1; i<=n; i++) { cin>>x[i]>>g[i]>>d[i]; g[i]+=g[i-1]; d[i]+=d[i-1]; } map<ll,ll> mp; // mono-decreasing auto insert = [&](ll k, ll v) { if (!mp.count(k)) { mp[k] = v; } else { mp[k] = max(mp[k], v); } auto iter = mp.lower_bound(k); if (iter == mp.begin()) return; --iter; while (true) { if (iter->second > v) break; auto it2 = iter; bool done = false; if (it2==mp.begin()) { done=true; } else { --it2; } mp.erase(iter); if (done) break; iter = it2; } }; auto check = [&]() { ll last = 1e18; for (auto p: mp) { if (p.second > last) return false; last = p.second; } return true; }; ll ans = 0; for (int i=1; i<=n; i++) { insert(x[i]-d[i-1], -g[i-1]); auto iter = mp.lower_bound(x[i]-d[i]); if (iter != mp.end()) { ans = max(ans, g[i]+iter->second); } assert(check()); } cout<<ans<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...