Submission #990147

#TimeUsernameProblemLanguageResultExecution timeMemory
990147tch1cherinDivide and conquer (IZhO14_divide)C++17
100 / 100
51 ms11348 KiB
#include <bits/stdc++.h> using namespace std; int main() { cin.tie(nullptr)->sync_with_stdio(false); int N; cin >> N; vector<int> x(N), g(N), d(N); for (int i = 0; i < N; i++) { cin >> x[i] >> g[i] >> d[i]; } vector<long long> pref_d(N + 1), pref_g(N + 1); for (int i = 0; i < N; i++) { pref_d[i + 1] = pref_d[i] + d[i]; pref_g[i + 1] = pref_g[i] + g[i]; } set<pair<long long, long long>> S; long long answer = 0; for (int i = 0; i < N; i++) { auto it = S.lower_bound({pref_d[i] - x[i], numeric_limits<int>::max()}); bool good = true; if (it != S.begin()) { if (prev(it)->second < pref_g[i]) { good = false; } } if (good) { while (it != S.end() && it->second >= pref_g[i]) { it = S.erase(it); } S.insert({pref_d[i] - x[i], pref_g[i]}); } it = S.lower_bound({pref_d[i + 1] - x[i], numeric_limits<int>::max()}); assert(it != S.begin()); answer = max(answer, pref_g[i + 1] - prev(it)->second); } cout << answer << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...