# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
527766 |
2022-02-18T08:56:28 Z |
KoD |
Cigle (COI21_cigle) |
C++17 |
|
3 ms |
3276 KB |
#include <bits/stdc++.h>
using std::vector;
using std::array;
using std::pair;
using std::tuple;
constexpr int M = 5000;
constexpr int inf = (1ll << 30) - 1;
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
int N;
std::cin >> N;
vector<int> D(N + 1);
for (int i = 0; i < N; ++i) {
std::cin >> D[i + 1];
D[i + 1] += D[i];
}
vector score(N + 1, vector(N + 1, 0));
for (int m = 0; m <= N; ++m) {
for (int l = m - 1, r = m, s = 0; l >= 0; --l) {
while (r <= N and D[m] - D[l] > D[r] - D[m]) {
r += 1;
}
if (r <= N) {
score[m][l] = s;
s += (D[m] - D[l] == D[r] - D[m]);
}
}
for (int r = m + 1, l = m, s = 0; r <= N; ++r) {
while (l >= 0 and D[r] - D[m] > D[m] - D[l]) {
l -= 1;
}
if (l >= 0) {
score[m][r] = s;
s += (D[m] - D[l] == D[r] - D[m]);
}
}
}
vector dp(N + 1, vector(N + 1, -inf));
vector max(N + 1, vector(N + 1, -inf));
for (int j = 1; j <= N; ++j) {
dp[0][j] = 0;
}
for (int i = 0; i <= N; ++i) {
int l = i, r = i;
for (int j = i; j <= N; ++j) {
if (i > 0) {
max[i][j] = std::max(max[i][j], max[i - 1][j]);
}
// l, i -> i, j
// D[i] - D[j] <= D[i] - D[l]
// dp[l][i] + score[i][j]
while (l >= 0 and D[j] - D[i] > D[i] - D[l]) {
l -= 1;
}
if (l >= 0) {
dp[i][j] = std::max(dp[i][j], dp[l][i] + score[i][j]);
}
if (j > 0) {
dp[i][j] = std::max(dp[i][j], dp[i][j - 1]);
}
max[i][j] = dp[i][j];
// i, j -> j, r
// D[j] - D[i] <= D[r] - D[j]
// dp[i][j] + score[j][i]
while (r <= N and D[j] - D[i] > D[r] - D[j]) {
r += 1;
}
if (r <= N) {
dp[j][r] = std::max(dp[j][r], dp[i][j] + score[j][i]);
}
}
}
int ans = 0;
for (const auto& v : dp) {
for (const auto& x : v) {
ans = std::max(ans, x);
}
}
std::cout << ans << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Incorrect |
1 ms |
308 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Incorrect |
1 ms |
308 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
3256 KB |
Output is correct |
2 |
Incorrect |
3 ms |
3276 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Incorrect |
1 ms |
308 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Incorrect |
1 ms |
308 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |