This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define ff first
#define ss second
#define pii pair<int, int>
#define all(v) (v).begin(), (v).end()
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
vector<int> a(n);
for (auto &i : a)
cin >> i;
vector<vector<ll>> dp(n, vector<ll>(n, LLONG_MAX));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
ll sm = 0;
for (int k = i; k >= 0; k--) {
sm += a[k];
if (j && k && dp[k - 1][j - 1] <= sm) {
dp[i][j] = sm; break;
}
}
if (!j) dp[i][0] = sm;
}
}
for (int i = 0; i <= n; i++)
if (i == n || dp[n - 1][i] == LLONG_MAX) return cout << i, 0;
}
// #include <bits/stdc++.h>
// using namespace std;
// using ll = long long;
// int main() {
// ios::sync_with_stdio(false); cin.tie(nullptr);
// int n;
// cin >> n;
// vector<int> a(n);
// for (auto &i : a)
// cin >> i;
// int mx = 1;
// for (int mk = 0; mk < 1 << n; mk++) {
// int cnt = 0;
// ll pre_sm = -1, sm = 0;
// for (int i = 0; i < n; i++) {
// if (!i || (((mk >> i) & 1) != ((mk >> (i - 1)) & 1))) {
// if (pre_sm > sm) {
// cnt = 0; break;
// }
// cnt++;
// pre_sm = sm; sm = 0;
// }
// sm += a[i];
// }
// if (pre_sm <= sm) mx = max(mx, cnt);
// }
// cout << mx;
// }
# | 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... |