#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 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... |