/**
_ _ __ _ _ _ _ _ _
|a ||t ||o d | |o |
| __ _| | _ | __| _ |
| __ |/_ | __ /__\ / _\|
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N_MAX = 10000;
const ll INF = LLONG_MAX / 2;
int N, K;
int A[N_MAX + 2];
ll dp[N_MAX + 2][N_MAX + 2];
ll cost[N_MAX + 2];
deque <int> rel[N_MAX + 2];
ll f (int j, int k) {
return dp[j][k] + cost[j + 1];
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> N >> K;
string S;
cin >> S;
for (int i = 0, j = 0; i < N * 2; i++) {
if (S[i] == 'A') {
A[++j] = i + 1;
}
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= i; j++) {
cost[j] += max(0, (A[i] - i) - (j - 1));
}
dp[i][0] = INF;
for (int k = 1; k <= K; k++) {
while (rel[k - 1].empty() == false && f(i - 1, k - 1) <= f(rel[k - 1].back(), k - 1)) {
rel[k - 1].pop_back();
}
rel[k - 1].push_back(i - 1);
while ((int) rel[k - 1].size() >= 2 && f(rel[k - 1][0], k - 1) >= f(rel[k - 1][1], k - 1)) {
rel[k - 1].pop_front();
}
if (rel[k - 1].empty() == true) {
dp[i][k] = INF;
} else {
dp[i][k] = f(rel[k - 1].front(), k - 1);
}
}
}
cout << dp[N][K] << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
8540 KB |
Output is correct |
2 |
Correct |
5 ms |
8548 KB |
Output is correct |
3 |
Correct |
3 ms |
8536 KB |
Output is correct |
4 |
Correct |
3 ms |
8540 KB |
Output is correct |
5 |
Correct |
3 ms |
8476 KB |
Output is correct |
6 |
Correct |
3 ms |
8540 KB |
Output is correct |
7 |
Correct |
4 ms |
8544 KB |
Output is correct |
8 |
Correct |
3 ms |
8540 KB |
Output is correct |
9 |
Correct |
4 ms |
8540 KB |
Output is correct |
10 |
Correct |
3 ms |
8540 KB |
Output is correct |
11 |
Correct |
5 ms |
8540 KB |
Output is correct |
12 |
Correct |
5 ms |
8540 KB |
Output is correct |
13 |
Correct |
5 ms |
8540 KB |
Output is correct |
14 |
Correct |
4 ms |
8536 KB |
Output is correct |
15 |
Correct |
5 ms |
8536 KB |
Output is correct |
16 |
Correct |
4 ms |
8540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
8540 KB |
Output is correct |
2 |
Correct |
5 ms |
8548 KB |
Output is correct |
3 |
Correct |
3 ms |
8536 KB |
Output is correct |
4 |
Correct |
3 ms |
8540 KB |
Output is correct |
5 |
Correct |
3 ms |
8476 KB |
Output is correct |
6 |
Correct |
3 ms |
8540 KB |
Output is correct |
7 |
Correct |
4 ms |
8544 KB |
Output is correct |
8 |
Correct |
3 ms |
8540 KB |
Output is correct |
9 |
Correct |
4 ms |
8540 KB |
Output is correct |
10 |
Correct |
3 ms |
8540 KB |
Output is correct |
11 |
Correct |
5 ms |
8540 KB |
Output is correct |
12 |
Correct |
5 ms |
8540 KB |
Output is correct |
13 |
Correct |
5 ms |
8540 KB |
Output is correct |
14 |
Correct |
4 ms |
8536 KB |
Output is correct |
15 |
Correct |
5 ms |
8536 KB |
Output is correct |
16 |
Correct |
4 ms |
8540 KB |
Output is correct |
17 |
Correct |
5 ms |
22872 KB |
Output is correct |
18 |
Correct |
11 ms |
47448 KB |
Output is correct |
19 |
Correct |
12 ms |
47452 KB |
Output is correct |
20 |
Correct |
8 ms |
47452 KB |
Output is correct |
21 |
Correct |
8 ms |
47452 KB |
Output is correct |
22 |
Correct |
10 ms |
47560 KB |
Output is correct |
23 |
Correct |
10 ms |
47448 KB |
Output is correct |
24 |
Correct |
8 ms |
47448 KB |
Output is correct |
25 |
Correct |
11 ms |
47448 KB |
Output is correct |
26 |
Correct |
10 ms |
47452 KB |
Output is correct |
27 |
Correct |
9 ms |
47644 KB |
Output is correct |
28 |
Correct |
10 ms |
47608 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
8540 KB |
Output is correct |
2 |
Correct |
5 ms |
8548 KB |
Output is correct |
3 |
Correct |
3 ms |
8536 KB |
Output is correct |
4 |
Correct |
3 ms |
8540 KB |
Output is correct |
5 |
Correct |
3 ms |
8476 KB |
Output is correct |
6 |
Correct |
3 ms |
8540 KB |
Output is correct |
7 |
Correct |
4 ms |
8544 KB |
Output is correct |
8 |
Correct |
3 ms |
8540 KB |
Output is correct |
9 |
Correct |
4 ms |
8540 KB |
Output is correct |
10 |
Correct |
3 ms |
8540 KB |
Output is correct |
11 |
Correct |
5 ms |
8540 KB |
Output is correct |
12 |
Correct |
5 ms |
8540 KB |
Output is correct |
13 |
Correct |
5 ms |
8540 KB |
Output is correct |
14 |
Correct |
4 ms |
8536 KB |
Output is correct |
15 |
Correct |
5 ms |
8536 KB |
Output is correct |
16 |
Correct |
4 ms |
8540 KB |
Output is correct |
17 |
Correct |
5 ms |
22872 KB |
Output is correct |
18 |
Correct |
11 ms |
47448 KB |
Output is correct |
19 |
Correct |
12 ms |
47452 KB |
Output is correct |
20 |
Correct |
8 ms |
47452 KB |
Output is correct |
21 |
Correct |
8 ms |
47452 KB |
Output is correct |
22 |
Correct |
10 ms |
47560 KB |
Output is correct |
23 |
Correct |
10 ms |
47448 KB |
Output is correct |
24 |
Correct |
8 ms |
47448 KB |
Output is correct |
25 |
Correct |
11 ms |
47448 KB |
Output is correct |
26 |
Correct |
10 ms |
47452 KB |
Output is correct |
27 |
Correct |
9 ms |
47644 KB |
Output is correct |
28 |
Correct |
10 ms |
47608 KB |
Output is correct |
29 |
Correct |
192 ms |
238420 KB |
Output is correct |
30 |
Correct |
246 ms |
288680 KB |
Output is correct |
31 |
Correct |
83 ms |
216656 KB |
Output is correct |
32 |
Correct |
37 ms |
196432 KB |
Output is correct |
33 |
Correct |
38 ms |
196272 KB |
Output is correct |
34 |
Correct |
334 ms |
302976 KB |
Output is correct |
35 |
Correct |
345 ms |
303396 KB |
Output is correct |
36 |
Correct |
38 ms |
196688 KB |
Output is correct |
37 |
Incorrect |
122 ms |
216144 KB |
Output isn't correct |
38 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
8540 KB |
Output is correct |
2 |
Correct |
5 ms |
8548 KB |
Output is correct |
3 |
Correct |
3 ms |
8536 KB |
Output is correct |
4 |
Correct |
3 ms |
8540 KB |
Output is correct |
5 |
Correct |
3 ms |
8476 KB |
Output is correct |
6 |
Correct |
3 ms |
8540 KB |
Output is correct |
7 |
Correct |
4 ms |
8544 KB |
Output is correct |
8 |
Correct |
3 ms |
8540 KB |
Output is correct |
9 |
Correct |
4 ms |
8540 KB |
Output is correct |
10 |
Correct |
3 ms |
8540 KB |
Output is correct |
11 |
Correct |
5 ms |
8540 KB |
Output is correct |
12 |
Correct |
5 ms |
8540 KB |
Output is correct |
13 |
Correct |
5 ms |
8540 KB |
Output is correct |
14 |
Correct |
4 ms |
8536 KB |
Output is correct |
15 |
Correct |
5 ms |
8536 KB |
Output is correct |
16 |
Correct |
4 ms |
8540 KB |
Output is correct |
17 |
Correct |
5 ms |
22872 KB |
Output is correct |
18 |
Correct |
11 ms |
47448 KB |
Output is correct |
19 |
Correct |
12 ms |
47452 KB |
Output is correct |
20 |
Correct |
8 ms |
47452 KB |
Output is correct |
21 |
Correct |
8 ms |
47452 KB |
Output is correct |
22 |
Correct |
10 ms |
47560 KB |
Output is correct |
23 |
Correct |
10 ms |
47448 KB |
Output is correct |
24 |
Correct |
8 ms |
47448 KB |
Output is correct |
25 |
Correct |
11 ms |
47448 KB |
Output is correct |
26 |
Correct |
10 ms |
47452 KB |
Output is correct |
27 |
Correct |
9 ms |
47644 KB |
Output is correct |
28 |
Correct |
10 ms |
47608 KB |
Output is correct |
29 |
Correct |
192 ms |
238420 KB |
Output is correct |
30 |
Correct |
246 ms |
288680 KB |
Output is correct |
31 |
Correct |
83 ms |
216656 KB |
Output is correct |
32 |
Correct |
37 ms |
196432 KB |
Output is correct |
33 |
Correct |
38 ms |
196272 KB |
Output is correct |
34 |
Correct |
334 ms |
302976 KB |
Output is correct |
35 |
Correct |
345 ms |
303396 KB |
Output is correct |
36 |
Correct |
38 ms |
196688 KB |
Output is correct |
37 |
Incorrect |
122 ms |
216144 KB |
Output isn't correct |
38 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
8540 KB |
Output is correct |
2 |
Correct |
5 ms |
8548 KB |
Output is correct |
3 |
Correct |
3 ms |
8536 KB |
Output is correct |
4 |
Correct |
3 ms |
8540 KB |
Output is correct |
5 |
Correct |
3 ms |
8476 KB |
Output is correct |
6 |
Correct |
3 ms |
8540 KB |
Output is correct |
7 |
Correct |
4 ms |
8544 KB |
Output is correct |
8 |
Correct |
3 ms |
8540 KB |
Output is correct |
9 |
Correct |
4 ms |
8540 KB |
Output is correct |
10 |
Correct |
3 ms |
8540 KB |
Output is correct |
11 |
Correct |
5 ms |
8540 KB |
Output is correct |
12 |
Correct |
5 ms |
8540 KB |
Output is correct |
13 |
Correct |
5 ms |
8540 KB |
Output is correct |
14 |
Correct |
4 ms |
8536 KB |
Output is correct |
15 |
Correct |
5 ms |
8536 KB |
Output is correct |
16 |
Correct |
4 ms |
8540 KB |
Output is correct |
17 |
Correct |
5 ms |
22872 KB |
Output is correct |
18 |
Correct |
11 ms |
47448 KB |
Output is correct |
19 |
Correct |
12 ms |
47452 KB |
Output is correct |
20 |
Correct |
8 ms |
47452 KB |
Output is correct |
21 |
Correct |
8 ms |
47452 KB |
Output is correct |
22 |
Correct |
10 ms |
47560 KB |
Output is correct |
23 |
Correct |
10 ms |
47448 KB |
Output is correct |
24 |
Correct |
8 ms |
47448 KB |
Output is correct |
25 |
Correct |
11 ms |
47448 KB |
Output is correct |
26 |
Correct |
10 ms |
47452 KB |
Output is correct |
27 |
Correct |
9 ms |
47644 KB |
Output is correct |
28 |
Correct |
10 ms |
47608 KB |
Output is correct |
29 |
Correct |
192 ms |
238420 KB |
Output is correct |
30 |
Correct |
246 ms |
288680 KB |
Output is correct |
31 |
Correct |
83 ms |
216656 KB |
Output is correct |
32 |
Correct |
37 ms |
196432 KB |
Output is correct |
33 |
Correct |
38 ms |
196272 KB |
Output is correct |
34 |
Correct |
334 ms |
302976 KB |
Output is correct |
35 |
Correct |
345 ms |
303396 KB |
Output is correct |
36 |
Correct |
38 ms |
196688 KB |
Output is correct |
37 |
Incorrect |
122 ms |
216144 KB |
Output isn't correct |
38 |
Halted |
0 ms |
0 KB |
- |