#include <bits/stdc++.h>
void solve() {
int n;
std::cin >> n;
std::vector<int64_t> a(n + 1);
for(int i = 1; i <= n; i++) {
std::cin >> a[i];
}
std::vector<int64_t> pref(n + 1);
for(int i = 1; i <= n; i++) {
pref[i] = pref[i - 1] + a[i];
}
std::vector<int> dp(n + 1, 0);
std::vector<int64_t> e(n + 1, 0);
dp[1] = 1;
e[1] = a[1];
for(int i = 2; i <= n; i++) {
for(int j = i - 1; j >= 0; j--) {
if(pref[i] >= pref[j] + e[j]) {
if(dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
e[i] = pref[i] - pref[j];
}
else if(dp[i] == dp[j] + 1) {
e[i] = std::min(e[i], pref[i] - pref[j]);
}
}
}
}
std::cout << dp[n];
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t = 1;
//std::cin >> t;
while (t--) {
solve();
}
return 0;
}
# | 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... |