Submission #1098746

#TimeUsernameProblemLanguageResultExecution timeMemory
1098746TurkhuuBigger segments (IZhO19_segments)C++17
13 / 100
0 ms456 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> a(n); for (auto &i : a) { cin >> i; } vector<ll> pfs(n + 1); vector<pair<int, ll>> dp(n + 1, {0, 0}); for (int i = 0, j = 0; i < n; i++) { pfs[i + 1] = pfs[i] + a[i]; if (pfs[i + 1] - pfs[j] >= -dp[j].second) { int lo = j, hi = i; while (lo < hi) { int mi = (lo + hi + 1) / 2; pfs[i + 1] - pfs[mi] >= -dp[mi].second ? lo = mi : hi = mi - 1; } dp[i + 1] = {dp[i].first + 1, pfs[lo] - pfs[i + 1]}; j = i + 1; } else { ll sum = 0; for (int j = i; j >= 0; j--) { sum += a[j]; auto [x, y] = dp[j]; if (-y <= sum) { dp[i + 1] = {x + 1, -sum}; break; } } } } cout << dp[n].first; return 6/22; }
#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...