This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// ↘ ⬇ ⬇ ⬇ ⬇ ⬇ ↙
// ➡ @roadfromroi ⬅
// ↗ ⬆ ⬆ ⬆ ⬆ ⬆ ↖
#include <iostream>
#include "vector"
#include "algorithm"
#include "numeric"
#include "climits"
#include "iomanip"
#include "bitset"
#include "cmath"
#include "map"
#include "deque"
#include "array"
#include "set"
#define all(x) x.begin(), x.end()
using namespace std;
#define int long long
void upd(pair<int, int> &a, pair<int, int> b) {
if (a.first < b.first)
a = b;
if (a.first == b.first)
a = min(a, b);
}
void solve() {
int n;
cin >> n;
vector<int> a(n);
vector<int> prf(n + 1);
for (int i = 0; i < n; ++i) {
cin >> a[i];
prf[i + 1] = prf[i] + a[i];
}
vector<pair<int, int>> dp(n + 1, {-1e9, 0});
dp[0] = {0, 0};
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j <= n; ++j) {
int vl = prf[j] - prf[i];
if (dp[i].second <= vl)
upd(dp[j], {dp[i].first + 1, vl});
}
}
cout << dp[n].first << '\n';
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t = 1;
while (t--) {
solve();
}
}
# | 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... |