Submission #862925

#TimeUsernameProblemLanguageResultExecution timeMemory
862925SanguineChameleonBigger segments (IZhO19_segments)C++17
100 / 100
75 ms43216 KiB
#include <bits/stdc++.h> using namespace std; void just_do_it(); int main() { #ifdef KAMIRULEZ freopen("kamirulez.inp", "r", stdin); freopen("kamirulez.out", "w", stdout); #endif ios_base::sync_with_stdio(0); cin.tie(0); just_do_it(); return 0; } const int maxn = 5e5 + 20; int a[maxn]; long long pref[maxn]; long long mi[maxn]; int dp[maxn]; vector<int> q[maxn]; bool cmp(long long val, int i) { return val < pref[i] + mi[i]; } void just_do_it() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; pref[i] = pref[i - 1] + a[i]; } q[0].push_back(0); int res = 0; for (int i = 1; i <= n; i++) { if (pref[q[res][0]] + mi[q[res][0]] <= pref[i]) { res++; } int j = *prev(upper_bound(q[res - 1].begin(), q[res - 1].end(), pref[i], cmp)); mi[i] = pref[i] - pref[j]; while (!q[res].empty() && pref[q[res].back()] + mi[q[res].back()] >= pref[i] + mi[i]) { q[res].pop_back(); } q[res].push_back(i); } cout << res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...