이 제출은 이전 버전의 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);
vector <long long> sp(1 + n);
vector <vector <int>> dp(1 + n, vector <int>(1 + n, -1));
int lastjump = 1;
for (int i = 1; i <= n; i++) {
cin >> v[i];
sp[i] = sp[i - 1] + v[i];
dp[i][1] = 0;
int cp = lastjump;
for (int jumps = max(1, lastjump - 1); jumps <= min(n, lastjump + 1); jumps++) {
int st, dr, mid;
st = 1; dr = i - 1;
while (st <= dr) {
mid = (st + dr) >> 1;
if (dp[mid][jumps - 1] == -1)
st = mid + 1;
else if (sp[i] - sp[mid] >= sp[mid] - sp[dp[mid][jumps - 1]]) {
st = mid + 1;
dp[i][jumps] = mid;
cp = max(cp, jumps);
} else
dr = mid - 1;
}
/*for (int j = 1; j < i; j++) {
if (dp[j][jumps - 1] != -1 && sp[i] - sp[j] >= sp[j] - sp[dp[j][jumps - 1]]) {
dp[i][jumps] = j;
cp = max(cp, jumps);
}
}*/
}
lastjump = cp;
}
/*for (int i = 1; i <= n; i++, cerr << '\n')
for (int j = 1; j <= n; j++)
cerr << dp[i][j] << '\t';*/
int maxjumps = 1;
for (int i = 1; i <= n; i++)
if (dp[n][i] != -1)
maxjumps = max(maxjumps, i);
cout << maxjumps << '\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... |