Submission #678120

#TimeUsernameProblemLanguageResultExecution timeMemory
678120AlcabelBigger segments (IZhO19_segments)C++17
13 / 100
1 ms324 KiB
#include <bits/stdc++.h> using namespace std; void solve() { int n; cin >> n; vector<int> a(n); vector<long long> pref(n + 1); for (int i = 0; i < n; ++i) { cin >> a[i]; pref[i + 1] = pref[i] + a[i]; } vector<pair<int, long long>> f(n + 1); f[0] = {0, 0}; for (int i = 1, lower = 0, cur = 0; i <= n; ++i) { int l = cur - 1, r = i; while (r - l > 1) { int m = l + (r - l) / 2; if (f[m].second <= pref[i] - pref[m]) { l = m; } else { r = m; } } if (l != cur - 1) { f[i] = {f[cur].first + 1, pref[i] - pref[l]}; lower = cur, cur = i; } else { l = lower - 1, r = cur; while (r - l > 1) { int m = l + (r - l) / 2; if (f[m].second <= pref[i] - pref[m]) { l = m; } else { r = m; } } assert(l != lower - 1); f[i] = {f[cur].first, pref[i] - pref[l]}; } // cerr << "i: " << i << ", f: " << f[i].first << ", " << f[i].second << '\n'; } cout << f[n].first << '\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int T = 1; // cin >> T; while (T--) { solve(); } return 0; }
#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...