Submission #1207975

#TimeUsernameProblemLanguageResultExecution timeMemory
1207975d4xnBigger segments (IZhO19_segments)C++17
0 / 100
0 ms320 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 5e5; int n, a[N], pre[N]; pair<int, int> dp[N]; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n; a[0] = pre[0] = 0; for (int i = 1; i <= n; i++) { cin >> a[i]; pre[i] = a[i] + pre[i-1]; dp[i] = make_pair(0, 69); } int r = 0; dp[0] = make_pair(1, -a[0]); for (int i = 0; i+1 < n; i++) { // no hago grupo nuevo dp[i+1] = max(dp[i+1], make_pair(dp[i].first, dp[i].second - a[i+1])); // hago grupo nuevo while (r < n && pre[r] - pre[i] < -dp[i].second) r++; if (r < n) dp[r] = max(dp[r], make_pair(dp[i].first + 1, pre[r] - pre[i])); } cout << dp[n-1].first << "\n"; }
#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...