Submission #1207981

#TimeUsernameProblemLanguageResultExecution timeMemory
1207981d4xnBigger segments (IZhO19_segments)C++17
0 / 100
0 ms328 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; for (int i = 0; i < n; i++) { cin >> a[i]; pre[i] = a[i] + (i ? pre[i-1] : 0); 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...