#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |