Submission #1207993

#TimeUsernameProblemLanguageResultExecution timeMemory
1207993d4xnBigger segments (IZhO19_segments)C++17
100 / 100
52 ms16032 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); } 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 int l = i+1; int r = n; while (l < r) { int mid = (l+r) >> 1; if (pre[mid] - pre[i] < -dp[i].second) l = mid+1; else r = mid; } if (l < n) dp[l] = max(dp[l], make_pair(dp[i].first + 1, -(pre[l] - 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...