Submission #334235

#TimeUsernameProblemLanguageResultExecution timeMemory
334235limabeansDivide and conquer (IZhO14_divide)C++17
48 / 100
1089 ms2796 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; auto insert = [&](ll k, ll v) { if (!mp.count(k)) { mp[k] = v; } else { mp[k] = max(mp[k], v); } }; auto print = [&]() { return; for (auto p: mp) cout<<p.first<<": "<<p.second<<endl; cout<<endl; }; 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]); for (; iter!=mp.end(); ++iter) { ans = max(ans, g[i] + iter->second); } print(); } cout<<ans<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...