# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
814365 | 2023-08-08T07:04:46 Z | reitracn | JJOOII 2 (JOI20_ho_t2) | C++17 | 29 ms | 19348 KB |
#include<bits/stdc++.h> using namespace std; #define int long long const int INF = 1e18; signed main() { int N, K; scanf("%lld%lld\n", &N, &K); vector<int > v(N); vector<int > nxt(N, INF); vector<deque<int >> deq(3); vector<vector<int>> dp(N+1, vector<int>(4, INF)); for(int iC = 0; iC < N; iC++) { char carLu; scanf("%c", &carLu); if(carLu == 'J') v[iC] = 0; else if(carLu == 'O') v[iC] = 1; else if(carLu == 'I') v[iC] = 2; else while (true) ; } for(int pos = 0; pos < N; pos++) { int colorAct = v[pos]; deq[colorAct].push_back(pos); if(deq[colorAct].size() == K) { int posFront = deq[colorAct].front(); deq[colorAct].pop_front(); nxt[posFront] = pos; } } /*for(int pos = 0; pos < N; pos++) { printf("%lld ", nxt[pos]); }*/ dp[0][0] = 0; int ans = INF; for(int pos = 0; pos< N; pos++) { for(int state = 0; state < 3; state ++) { if(state == 0) dp[pos+1][state] = min(dp[pos+1][state], dp[pos][state]); else dp[pos+1][state] = min(dp[pos+1][state], dp[pos][state] + 1); if(nxt[pos] != INF && v[pos] == state) { dp[nxt[pos] +1][state+1] = min(dp[nxt[pos] +1][state+1], dp[pos][state] + (nxt[pos] - pos +1) - K); if(state == 2) { ans = min(ans, dp[nxt[pos] +1 ][state+1]); } } } } if(ans == INF) printf("-1"); else printf("%lld\n", ans); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 296 KB | Output is correct |
4 | Correct | 1 ms | 212 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 0 ms | 212 KB | Output is correct |
7 | Correct | 1 ms | 300 KB | Output is correct |
8 | Correct | 1 ms | 212 KB | Output is correct |
9 | Correct | 0 ms | 212 KB | Output is correct |
10 | Correct | 1 ms | 296 KB | Output is correct |
11 | Correct | 1 ms | 244 KB | Output is correct |
12 | Correct | 1 ms | 212 KB | Output is correct |
13 | Correct | 1 ms | 212 KB | Output is correct |
14 | Correct | 1 ms | 212 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 296 KB | Output is correct |
4 | Correct | 1 ms | 212 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 0 ms | 212 KB | Output is correct |
7 | Correct | 1 ms | 300 KB | Output is correct |
8 | Correct | 1 ms | 212 KB | Output is correct |
9 | Correct | 0 ms | 212 KB | Output is correct |
10 | Correct | 1 ms | 296 KB | Output is correct |
11 | Correct | 1 ms | 244 KB | Output is correct |
12 | Correct | 1 ms | 212 KB | Output is correct |
13 | Correct | 1 ms | 212 KB | Output is correct |
14 | Correct | 1 ms | 212 KB | Output is correct |
15 | Correct | 1 ms | 468 KB | Output is correct |
16 | Correct | 1 ms | 468 KB | Output is correct |
17 | Correct | 1 ms | 468 KB | Output is correct |
18 | Correct | 1 ms | 468 KB | Output is correct |
19 | Correct | 1 ms | 468 KB | Output is correct |
20 | Correct | 1 ms | 468 KB | Output is correct |
21 | Correct | 1 ms | 468 KB | Output is correct |
22 | Correct | 1 ms | 468 KB | Output is correct |
23 | Correct | 1 ms | 340 KB | Output is correct |
24 | Correct | 1 ms | 468 KB | Output is correct |
25 | Correct | 1 ms | 468 KB | Output is correct |
26 | Correct | 1 ms | 560 KB | Output is correct |
27 | Correct | 1 ms | 552 KB | Output is correct |
28 | Correct | 1 ms | 468 KB | Output is correct |
29 | Correct | 1 ms | 468 KB | Output is correct |
30 | Correct | 1 ms | 468 KB | Output is correct |
31 | Correct | 1 ms | 340 KB | Output is correct |
32 | Correct | 1 ms | 468 KB | Output is correct |
33 | Correct | 1 ms | 468 KB | Output is correct |
34 | Correct | 1 ms | 468 KB | Output is correct |
35 | Correct | 1 ms | 556 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 296 KB | Output is correct |
4 | Correct | 1 ms | 212 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 0 ms | 212 KB | Output is correct |
7 | Correct | 1 ms | 300 KB | Output is correct |
8 | Correct | 1 ms | 212 KB | Output is correct |
9 | Correct | 0 ms | 212 KB | Output is correct |
10 | Correct | 1 ms | 296 KB | Output is correct |
11 | Correct | 1 ms | 244 KB | Output is correct |
12 | Correct | 1 ms | 212 KB | Output is correct |
13 | Correct | 1 ms | 212 KB | Output is correct |
14 | Correct | 1 ms | 212 KB | Output is correct |
15 | Correct | 1 ms | 468 KB | Output is correct |
16 | Correct | 1 ms | 468 KB | Output is correct |
17 | Correct | 1 ms | 468 KB | Output is correct |
18 | Correct | 1 ms | 468 KB | Output is correct |
19 | Correct | 1 ms | 468 KB | Output is correct |
20 | Correct | 1 ms | 468 KB | Output is correct |
21 | Correct | 1 ms | 468 KB | Output is correct |
22 | Correct | 1 ms | 468 KB | Output is correct |
23 | Correct | 1 ms | 340 KB | Output is correct |
24 | Correct | 1 ms | 468 KB | Output is correct |
25 | Correct | 1 ms | 468 KB | Output is correct |
26 | Correct | 1 ms | 560 KB | Output is correct |
27 | Correct | 1 ms | 552 KB | Output is correct |
28 | Correct | 1 ms | 468 KB | Output is correct |
29 | Correct | 1 ms | 468 KB | Output is correct |
30 | Correct | 1 ms | 468 KB | Output is correct |
31 | Correct | 1 ms | 340 KB | Output is correct |
32 | Correct | 1 ms | 468 KB | Output is correct |
33 | Correct | 1 ms | 468 KB | Output is correct |
34 | Correct | 1 ms | 468 KB | Output is correct |
35 | Correct | 1 ms | 556 KB | Output is correct |
36 | Correct | 19 ms | 16468 KB | Output is correct |
37 | Correct | 21 ms | 17720 KB | Output is correct |
38 | Correct | 23 ms | 17716 KB | Output is correct |
39 | Correct | 24 ms | 17648 KB | Output is correct |
40 | Correct | 25 ms | 18112 KB | Output is correct |
41 | Correct | 24 ms | 17840 KB | Output is correct |
42 | Correct | 22 ms | 17748 KB | Output is correct |
43 | Correct | 18 ms | 11384 KB | Output is correct |
44 | Correct | 20 ms | 14216 KB | Output is correct |
45 | Correct | 29 ms | 18232 KB | Output is correct |
46 | Correct | 24 ms | 18316 KB | Output is correct |
47 | Correct | 23 ms | 18228 KB | Output is correct |
48 | Correct | 23 ms | 18244 KB | Output is correct |
49 | Correct | 18 ms | 12256 KB | Output is correct |
50 | Correct | 28 ms | 18228 KB | Output is correct |
51 | Correct | 24 ms | 18316 KB | Output is correct |
52 | Correct | 23 ms | 18340 KB | Output is correct |
53 | Correct | 25 ms | 19124 KB | Output is correct |
54 | Correct | 19 ms | 17608 KB | Output is correct |
55 | Correct | 22 ms | 18752 KB | Output is correct |
56 | Correct | 21 ms | 19348 KB | Output is correct |