#include "paint.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int inf = 2e4+9,MX = 1e9+9;
int n,m,k;
int a[inf];
//vector<int> Cont[inf];
int LCS[inf][2009],dp[inf];
bool valid[inf];
bool liked[2009][inf*10];
bool like(int i,int j){
return liked[j][ a[i] ];
}
int minimumInstructions(int N, int M, int K, vector<int> C,
vector<int> A,vector<vector<int>> B) {
n = N, m = M,k = K;
for(int i=1;i<=n;i++)
a[i] = C[i-1]+1;
for(int i=1;i<=m;i++){
for(auto o:B[i-1]){
assert(o+1 <= n);
liked[i][o+1] = 1;
}
}
for(int i=n;i>=1;i--){
for(int j=m;j>=1;j--){
if(like(i,j))
LCS[i][j] = LCS[i+1][j+1] + 1;
else
LCS[i][j] = 0;
}
}
for(int y=1;y <= n-m+1;y++){
for(int x = 1;x <= m;x++){
int len1 = m-x+1,i1 = y,j1 = x,tmp1;
tmp1 = LCS[i1][j1];
int len2 = x-1,i2 = y+len1,j2 = 1,tmp2 = 0;
if(len2)
tmp2 = LCS[i2][j2];
valid[y] |= (tmp1 >= len1 && tmp2 >= len2);
}
}
for(int i=1;i<=n;i++)
dp[i] = MX;
dp[n-m+1] = (valid[n-m+1]?1:MX);
for(int i=n-m;i>=1;i--)
for(int j=i+1;j<=i+m && valid[i];j++)
dp[i] = min(dp[i],dp[j] + 1);
return ( (dp[1] == MX)?-1:dp[1]);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
0 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
2304 KB |
Output is correct |
8 |
Correct |
2 ms |
2304 KB |
Output is correct |
9 |
Correct |
1 ms |
2304 KB |
Output is correct |
10 |
Correct |
2 ms |
2432 KB |
Output is correct |
11 |
Correct |
2 ms |
2432 KB |
Output is correct |
12 |
Correct |
2 ms |
2432 KB |
Output is correct |
13 |
Runtime error |
28 ms |
512 KB |
Execution killed with signal 11 |
14 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
2304 KB |
Output is correct |
10 |
Correct |
2 ms |
2304 KB |
Output is correct |
11 |
Correct |
1 ms |
2304 KB |
Output is correct |
12 |
Correct |
2 ms |
2432 KB |
Output is correct |
13 |
Correct |
2 ms |
2432 KB |
Output is correct |
14 |
Correct |
2 ms |
2432 KB |
Output is correct |
15 |
Runtime error |
28 ms |
512 KB |
Execution killed with signal 11 |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
2304 KB |
Output is correct |
10 |
Correct |
2 ms |
2304 KB |
Output is correct |
11 |
Correct |
1 ms |
2304 KB |
Output is correct |
12 |
Correct |
2 ms |
2432 KB |
Output is correct |
13 |
Correct |
2 ms |
2432 KB |
Output is correct |
14 |
Correct |
2 ms |
2432 KB |
Output is correct |
15 |
Runtime error |
28 ms |
512 KB |
Execution killed with signal 11 |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
2304 KB |
Output is correct |
10 |
Correct |
2 ms |
2304 KB |
Output is correct |
11 |
Correct |
1 ms |
2304 KB |
Output is correct |
12 |
Correct |
2 ms |
2432 KB |
Output is correct |
13 |
Correct |
2 ms |
2432 KB |
Output is correct |
14 |
Correct |
2 ms |
2432 KB |
Output is correct |
15 |
Runtime error |
28 ms |
512 KB |
Execution killed with signal 11 |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
0 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
0 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
2304 KB |
Output is correct |
10 |
Correct |
2 ms |
2304 KB |
Output is correct |
11 |
Correct |
1 ms |
2304 KB |
Output is correct |
12 |
Correct |
2 ms |
2432 KB |
Output is correct |
13 |
Correct |
2 ms |
2432 KB |
Output is correct |
14 |
Correct |
2 ms |
2432 KB |
Output is correct |
15 |
Runtime error |
28 ms |
512 KB |
Execution killed with signal 11 |
16 |
Halted |
0 ms |
0 KB |
- |