이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#ifdef BLAT
#include "debug/debug.hpp"
#else
#define debug(x...)
#endif
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector <int> v(1 + n), dp(1 + n);
vector <long long> sp(1 + n), s(1 + n);
dp[1] = 1;
for (int i = 1; i <= n; i++) {
cin >> v[i];
sp[i] = sp[i - 1] + v[i];
dp[i] = dp[i - 1];
s[i] = s[i - 1] + v[i];
for (int j = 1; j < i; j++) {
if (sp[i] - sp[j] >= s[j]) {
if (dp[j] + 1 == dp[i])
s[i] = min(s[i], sp[i] - sp[j]);
else if (dp[j] + 1 > dp[i]) {
s[i] = sp[i] - sp[j];
dp[i] = 1 + dp[j];
}
}
}
}
cout << dp[n] + 1 << '\n';
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... |