# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
387131 | 2021-04-08T03:17:24 Z | milleniumEeee | Painting Walls (APIO20_paint) | C++17 | 1500 ms | 8940 KB |
#include <bits/stdc++.h> #include "paint.h" //#include "grader.cpp" using namespace std; const int MAXN = (int)1e5 + 5; const int INF = 1e9 + 7; int pos[MAXN]; int dp[MAXN]; int pref[MAXN]; int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) { memset(pos, -1, sizeof(pos)); for (int i = 0; i < M; i++) { for (int el : B[i]) { pos[el] = i; } } for (int i = 0; i < N; i++) { if (pos[C[i]] == -1) { return -1; } } auto nxt = [&](int p) { if (p + 1 < M) { return p + 1; } else { return 0; } }; for (int i = 0; i + 1 < N; i++) { int before = (i > 0 ? pref[i - 1] : 0); pref[i] = before + (pos[C[i + 1]] == nxt(pos[C[i]])); } auto get = [&](int l, int r) { return pref[r - 1] - pref[l - 1]; }; auto can = [&](int l, int r) { if (r - l + 1 == M && get(l, r) == M - 1) { return true; } else { return false; } }; fill(dp, dp + MAXN, INF); if (can(0, M - 1)) { for (int i = 0; i < M; i++) { dp[i] = 1; } } for (int i = M; i < N; i++) { if (can(i - M + 1, i)) { int best = INF; for (int j = i - M; j < i; j++) { if (j >= 0) { best = min(best, dp[j]); } } dp[i] = best + 1; for (int j = i - M + 1; j <= i; j++) { dp[j] = min(dp[j], dp[i]); } } } if (dp[N - 1] < INF) { return dp[N - 1]; } else { return -1; } } /* 5 3 10 0 2 1 4 3 2 0 4 2 3 2 1 1 */
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 1132 KB | Output is correct |
2 | Correct | 2 ms | 1132 KB | Output is correct |
3 | Correct | 1 ms | 748 KB | Output is correct |
4 | Correct | 1 ms | 1132 KB | Output is correct |
5 | Correct | 1 ms | 1132 KB | Output is correct |
6 | Correct | 2 ms | 1132 KB | Output is correct |
7 | Correct | 2 ms | 1132 KB | Output is correct |
8 | Correct | 2 ms | 1132 KB | Output is correct |
9 | Correct | 2 ms | 1152 KB | Output is correct |
10 | Correct | 2 ms | 1132 KB | Output is correct |
11 | Correct | 1 ms | 1132 KB | Output is correct |
12 | Correct | 1 ms | 1132 KB | Output is correct |
13 | Correct | 2 ms | 1132 KB | Output is correct |
14 | Correct | 2 ms | 1132 KB | Output is correct |
15 | Correct | 2 ms | 1132 KB | Output is correct |
16 | Correct | 2 ms | 1132 KB | Output is correct |
17 | Correct | 2 ms | 1132 KB | Output is correct |
18 | Correct | 2 ms | 1132 KB | Output is correct |
19 | Correct | 2 ms | 748 KB | Output is correct |
20 | Correct | 2 ms | 748 KB | Output is correct |
21 | Correct | 2 ms | 748 KB | Output is correct |
22 | Correct | 17 ms | 2540 KB | Output is correct |
23 | Correct | 15 ms | 2412 KB | Output is correct |
24 | Correct | 14 ms | 2412 KB | Output is correct |
25 | Correct | 4 ms | 1388 KB | Output is correct |
26 | Correct | 4 ms | 1388 KB | Output is correct |
27 | Correct | 4 ms | 1408 KB | Output is correct |
28 | Correct | 4 ms | 1388 KB | Output is correct |
29 | Correct | 4 ms | 1388 KB | Output is correct |
30 | Correct | 4 ms | 1388 KB | Output is correct |
31 | Correct | 80 ms | 2020 KB | Output is correct |
32 | Correct | 80 ms | 1900 KB | Output is correct |
33 | Correct | 80 ms | 1900 KB | Output is correct |
34 | Correct | 80 ms | 1900 KB | Output is correct |
35 | Correct | 81 ms | 1900 KB | Output is correct |
36 | Correct | 80 ms | 1900 KB | Output is correct |
37 | Correct | 18 ms | 2924 KB | Output is correct |
38 | Correct | 18 ms | 2924 KB | Output is correct |
39 | Correct | 18 ms | 2924 KB | Output is correct |
40 | Correct | 12 ms | 2304 KB | Output is correct |
41 | Correct | 8 ms | 1900 KB | Output is correct |
42 | Correct | 14 ms | 2412 KB | Output is correct |
43 | Correct | 9 ms | 2028 KB | Output is correct |
44 | Correct | 8 ms | 1900 KB | Output is correct |
45 | Correct | 13 ms | 2412 KB | Output is correct |
46 | Execution timed out | 1562 ms | 8940 KB | Time limit exceeded |
47 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 1132 KB | Output is correct |
2 | Correct | 2 ms | 1132 KB | Output is correct |
3 | Correct | 1 ms | 748 KB | Output is correct |
4 | Correct | 1 ms | 1132 KB | Output is correct |
5 | Correct | 1 ms | 1132 KB | Output is correct |
6 | Correct | 2 ms | 1132 KB | Output is correct |
7 | Correct | 2 ms | 1132 KB | Output is correct |
8 | Correct | 2 ms | 1132 KB | Output is correct |
9 | Correct | 2 ms | 1152 KB | Output is correct |
10 | Correct | 2 ms | 1132 KB | Output is correct |
11 | Correct | 1 ms | 1132 KB | Output is correct |
12 | Correct | 1 ms | 1132 KB | Output is correct |
13 | Correct | 2 ms | 1132 KB | Output is correct |
14 | Correct | 2 ms | 1132 KB | Output is correct |
15 | Correct | 2 ms | 1132 KB | Output is correct |
16 | Correct | 2 ms | 1132 KB | Output is correct |
17 | Correct | 2 ms | 1132 KB | Output is correct |
18 | Correct | 2 ms | 1132 KB | Output is correct |
19 | Correct | 2 ms | 748 KB | Output is correct |
20 | Correct | 2 ms | 748 KB | Output is correct |
21 | Correct | 2 ms | 748 KB | Output is correct |
22 | Incorrect | 2 ms | 1132 KB | Output isn't correct |
23 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 1132 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 1132 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 1132 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |