QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #357278 | #5035. foo~ | zyc070419 | 10 | 175ms | 43132kb | C++14 | 1.4kb | 2024-03-18 19:54:52 | 2024-03-18 19:54:53 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
int n, k, A[N], pos, Pos, a[N], val[N][N], dp[2][N], opt, ans = -1e9;
void work() {
for (int l = 1; l <= n; ++l)
for (int r = l, mx = -1, now = 0; r <= n; ++r) {
if (a[r] > mx) mx = a[r], now++;
val[l][r] = now;
}
for (int r = n; r >= 1; --r)
for (int l = r, mx = -1, now = 0; l >= 1; --l) {
if (a[l] > mx) mx = a[l], now++;
val[l][r] = max(val[l][r], now);
}
for (int i = 0; i <= n; ++i) dp[0][i] = dp[1][i] = -1e9;
dp[opt][0] = 0;
for (int o = 1; o <= k; ++o) {
opt ^= 1;
for (int i = 1; i <= n; ++i) {
dp[opt][i] = -1e9;
for (int j = o; j <= i; ++j) dp[opt][i] = max(dp[opt][i], dp[opt ^ 1][j - 1] + val[j][i]);
}
}
ans = max(dp[opt][n], ans);
}
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; ++i) {
scanf("%d", &A[i]);
if (A[i] == n) pos = i;
if (A[i] == 1) Pos = 1;
}
for (int i = pos, j = 1; j <= n; ++i, ++j) {
if (i > n) i -= n;
a[j] = A[i];
}
work();
for (int i = pos + 1, j = 1; j <= n; ++i, ++j) {
if (i > n) i -= n;
a[j] = A[i];
}
work();
for (int i = Pos, j = 1; j <= n; ++i, ++j) {
if (i > n) i -= n;
a[j] = A[i];
}
work();
for (int i = Pos + 1, j = 1; j <= n; ++i, ++j) {
if (i > n) i -= n;
a[j] = A[i];
}
work();
return printf("%d\n", ans), 0;
}
/*
18 1
1 3 5 7 9 11 13 15 17 18 16 14 12 10 8 6 4 2
*/
详细
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 0ms
memory: 3988kb
input:
23 6 16 20 22 4 21 10 3 7 5 8 15 12 9 1 6 17 23 13 11 19 18 14 2
output:
20
result:
ok "20"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3868kb
input:
13 6 13 9 3 4 12 6 5 1 8 10 11 7 2
output:
13
result:
ok "13"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
25 3 25 2 3 19 5 6 7 11 8 10 9 20 4 14 21 1 17 12 13 18 15 22 23 16 24
output:
16
result:
ok "16"
Test #4:
score: 0
Accepted
time: 0ms
memory: 4028kb
input:
25 9 1 11 10 23 9 24 7 8 19 3 5 21 18 12 15 16 17 13 2 20 14 22 4 6 25
output:
23
result:
ok "23"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
13 2 1 4 2 3 5 6 7 8 9 10 12 11 13
output:
12
result:
ok "12"
Test #6:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
17 5 4 2 3 6 5 1 7 8 13 16 11 12 9 14 15 10 17
output:
15
result:
ok "15"
Test #7:
score: 0
Accepted
time: 0ms
memory: 5904kb
input:
8 2 1 2 5 6 3 4 7 8
output:
8
result:
ok "8"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3940kb
input:
11 5 3 11 2 10 6 5 1 4 8 7 9
output:
11
result:
ok "11"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3876kb
input:
10 1 5 3 4 1 10 8 9 6 7 2
output:
6
result:
ok "6"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3960kb
input:
16 2 15 12 14 9 11 13 1 3 10 8 5 2 16 4 6 7
output:
9
result:
ok "9"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3920kb
input:
6 3 4 1 5 6 2 3
output:
6
result:
ok "6"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3932kb
input:
1 1 1
output:
1
result:
ok "1"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3992kb
input:
16 5 7 14 13 16 10 1 9 11 3 8 2 4 5 15 12 6
output:
14
result:
ok "14"
Test #14:
score: 0
Accepted
time: 0ms
memory: 3936kb
input:
10 3 10 1 7 2 8 6 9 5 4 3
output:
9
result:
ok "9"
Test #15:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
23 9 12 11 22 2 5 9 1 4 18 19 17 16 23 20 6 13 8 21 10 7 14 15 3
output:
23
result:
ok "23"
Test #16:
score: 0
Accepted
time: 0ms
memory: 3984kb
input:
15 4 4 3 8 13 12 1 14 9 15 10 7 11 2 6 5
output:
13
result:
ok "13"
Test #17:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
24 7 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
output:
24
result:
ok "24"
Test #18:
score: 0
Accepted
time: 0ms
memory: 3944kb
input:
4 2 1 2 3 4
output:
4
result:
ok "4"
Test #19:
score: 0
Accepted
time: 0ms
memory: 3968kb
input:
18 1 1 3 5 7 9 11 13 15 17 18 16 14 12 10 8 6 4 2
output:
10
result:
ok "10"
Test #20:
score: 0
Accepted
time: 0ms
memory: 4000kb
input:
18 2 1 3 5 7 9 11 13 15 17 18 16 14 12 10 8 6 4 2
output:
18
result:
ok "18"
Subtask #2:
score: 0
Runtime Error
Test #21:
score: 0
Runtime Error
input:
93943 1 87243 48984 50611 19218 77699 25025 85769 28141 13380 34875 42459 66419 53472 4367 48292 16894 92171 87263 42527 67085 30687 29235 27515 81053 31421 34864 83591 70491 75344 7026 50250 63402 26773 5330 36308 76399 80032 15501 16205 71750 73964 67876 68901 70548 2043 79979 89479 19784 38838 44...
output:
result:
Subtask #3:
score: 0
Wrong Answer
Test #36:
score: 0
Wrong Answer
time: 175ms
memory: 43132kb
input:
1992 25 144 612 1315 1966 1779 1773 1529 625 36 1849 1783 1441 1388 1558 1258 724 137 397 542 353 1162 1213 406 792 1317 882 994 298 1864 1969 103 449 508 1501 89 1721 195 778 657 222 1152 1780 613 743 1206 694 829 142 69 1973 1465 1343 655 1540 155 146 350 491 759 1695 1082 1357 1329 1745 232 1850 ...
output:
236
result:
wrong answer 1st words differ - expected: '237', found: '236'
Subtask #4:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #2:
0%