#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#define print(x) cout << x << endl
#pragma GCC optimize ("O3")
#pragma GCC optimize ("O2")
//#define endl '\n'
//#define int long long
using namespace std;
int subtask1(int N, int M, int K, vt<int> C, vt<int> A, vt<vt<int>> B)
{
map<int, int> MP;
for(int i = 0; i < M; i++)
{
for(int x : B[i])
{
MP[x] = i + 1;
}
}
int i, j, ans;
i = j = ans = 0;
while(i <= N - M)
{
if (MP[C[i]] == 0) return -1;
j = i + 1;
while(j < N)
{
if (MP[C[j]] - 1 != MP[C[j - 1]] % M) break;
j++;
}
j--;
if (j - i + 1 < M) return -1;
ans += (j - i + M) / M;
i = j + 1;
}
if (i != N) return -1;
return ans;
}
int minimumInstructions(int N, int M, int K, vt<int> C, vt<int> A, vt<vt<int>> B)
{
map<int, int> MP;
bool sub1 = 1;
for(int i = 0; i < M; i++)
{
for(int x : B[i])
{
if (MP[x])
{
sub1 = 0;
break;
}
MP[x] = 1;
}
}
if (sub1) return subtask1(N, M, K, C, A, B);
vt<int> dp(N);
int i = 0;
while(i <= N - M)
{
if (i > 0 && !dp[i - 1]) continue;
for(int master = 0; master < M; master++)
{
int m = master;
int j = i;
while(j < N)
{
int tmp = lower_bound(all(B[m]), C[j]) - B[m].begin();
if (B[m][tmp] != C[j]) break;
m = (m + 1) % M;
j++;
}
if (j - i + 1 < M) continue;
int tmp = i > 0 ? dp[i - 1] : 0;
dp[j] = !dp[j] ? (i + j + m) / M + tmp : min(dp[j], (i + j + m) / M + tmp);
}
i++;
}
if (dp[N - 1]) return dp[N - 1];
return -1;
}
/**
main()
{
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int ans = minimumInstructions(6, 4, 4, {2, 1, 0, 3, 2, 1}, {3}, {{2}, {1}, {0}, {3}});
print(ans);
}
/**/
Compilation message
paint.cpp:104:1: warning: "/*" within comment [-Wcomment]
104 | /**/
|
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
2 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
300 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
336 KB |
Output is correct |
18 |
Correct |
1 ms |
336 KB |
Output is correct |
19 |
Correct |
2 ms |
332 KB |
Output is correct |
20 |
Correct |
2 ms |
332 KB |
Output is correct |
21 |
Correct |
2 ms |
332 KB |
Output is correct |
22 |
Correct |
83 ms |
11076 KB |
Output is correct |
23 |
Correct |
87 ms |
11012 KB |
Output is correct |
24 |
Correct |
85 ms |
11252 KB |
Output is correct |
25 |
Correct |
3 ms |
460 KB |
Output is correct |
26 |
Correct |
3 ms |
460 KB |
Output is correct |
27 |
Correct |
3 ms |
460 KB |
Output is correct |
28 |
Correct |
3 ms |
564 KB |
Output is correct |
29 |
Correct |
3 ms |
564 KB |
Output is correct |
30 |
Correct |
3 ms |
460 KB |
Output is correct |
31 |
Correct |
26 ms |
3024 KB |
Output is correct |
32 |
Correct |
25 ms |
3020 KB |
Output is correct |
33 |
Correct |
31 ms |
3052 KB |
Output is correct |
34 |
Correct |
25 ms |
3020 KB |
Output is correct |
35 |
Correct |
27 ms |
3084 KB |
Output is correct |
36 |
Correct |
27 ms |
3140 KB |
Output is correct |
37 |
Correct |
98 ms |
11484 KB |
Output is correct |
38 |
Correct |
97 ms |
11488 KB |
Output is correct |
39 |
Correct |
107 ms |
11488 KB |
Output is correct |
40 |
Correct |
10 ms |
1480 KB |
Output is correct |
41 |
Correct |
7 ms |
972 KB |
Output is correct |
42 |
Correct |
11 ms |
1612 KB |
Output is correct |
43 |
Correct |
8 ms |
1100 KB |
Output is correct |
44 |
Correct |
9 ms |
1100 KB |
Output is correct |
45 |
Correct |
11 ms |
1612 KB |
Output is correct |
46 |
Correct |
144 ms |
18184 KB |
Output is correct |
47 |
Correct |
89 ms |
10612 KB |
Output is correct |
48 |
Correct |
93 ms |
14404 KB |
Output is correct |
49 |
Correct |
106 ms |
16016 KB |
Output is correct |
50 |
Correct |
118 ms |
15536 KB |
Output is correct |
51 |
Correct |
85 ms |
11460 KB |
Output is correct |
52 |
Correct |
13 ms |
1656 KB |
Output is correct |
53 |
Correct |
11 ms |
1660 KB |
Output is correct |
54 |
Correct |
12 ms |
1612 KB |
Output is correct |
55 |
Correct |
11 ms |
1664 KB |
Output is correct |
56 |
Correct |
11 ms |
1612 KB |
Output is correct |
57 |
Correct |
11 ms |
1612 KB |
Output is correct |
58 |
Correct |
165 ms |
19908 KB |
Output is correct |
59 |
Correct |
168 ms |
19804 KB |
Output is correct |
60 |
Correct |
174 ms |
19824 KB |
Output is correct |
61 |
Correct |
169 ms |
19924 KB |
Output is correct |
62 |
Correct |
172 ms |
20020 KB |
Output is correct |
63 |
Correct |
164 ms |
19908 KB |
Output is correct |
64 |
Correct |
130 ms |
18688 KB |
Output is correct |
65 |
Correct |
132 ms |
18732 KB |
Output is correct |
66 |
Correct |
143 ms |
18756 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
1 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
1 ms |
204 KB |
Output is correct |
9 |
Correct |
2 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
204 KB |
Output is correct |
11 |
Correct |
1 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
300 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
336 KB |
Output is correct |
18 |
Correct |
1 ms |
336 KB |
Output is correct |
19 |
Correct |
2 ms |
332 KB |
Output is correct |
20 |
Correct |
2 ms |
332 KB |
Output is correct |
21 |
Correct |
2 ms |
332 KB |
Output is correct |
22 |
Execution timed out |
1587 ms |
204 KB |
Time limit exceeded |
23 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1587 ms |
204 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1587 ms |
204 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1587 ms |
204 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |