#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> a;
vector<int> prfx;
vector< vector<int> > memo;
// Compute prefix sum from l to r
int getPrfx(int l, int r) {
int left = (l == 0) ? 0 : prfx[l - 1];
int right = prfx[r];
return right - left;
}
// Custom comparison function
bool compare(const vector<int>& s1, const vector<int>& s2) {
if (s1[0] > s2[0]) return true;
if (s1[0] < s2[0]) return false;
return s1[1] < s2[1];
}
// DP function
vector<int> dp(int i) {
if (i < 0) return vector<int>{1, 0};
if (memo[i][0] != -1) return memo[i];
vector<int> res = dp(i - 1);
res[1] += a[i];
for (int j = 0; j < i; ++j) {
vector<int> c = dp(j);
int s = getPrfx(j + 1, i);
if (s < c[1]) continue;
c[1] = s;
c[0] += 1;
if (compare(c, res)) res = c;
}
memo[i] = res;
return res;
}
signed main() {
int n;
cin >> n;
a.resize(n);
for (int i = 0; i < n; ++i) cin >> a[i];
prfx.resize(n);
prfx[0] = a[1];
for (int i = 1; i < n; ++i) {
prfx[i] = prfx[i - 1] + a[i];
}
memo.assign(n, vector<int>(2, -1));
vector<int> result = dp(n - 1);
cout << result[0] << endl;
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... |