# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
375348 | 2021-03-09T09:43:18 Z | astoria | Painting Walls (APIO20_paint) | C++14 | 6 ms | 5356 KB |
#include "bits/stdc++.h" #include "paint.h" using namespace std; int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B){ vector<int> f[K+5]; //for the colour i, who can do? for(int i=0; i<M; i++){ for(int j=0; j<A[i]; j++){ int col = B[i][j]; f[col].push_back(i); } } int lng[N+5]; memset(lng,-1,sizeof(lng)); for(int j : f[C[0]]) lng[0]=1; lng[0]=max(lng[0],0); for(int i=1; i<N; i++){ for(int j : f[C[i]]){ lng[i] = 1; int lst = j-1; if(lst<0) lst+=M; if(f[C[i-1]].front()==lst) lng[i] += lng[i-1]; } lng[i]=max(lng[i],0); } int dp[N+5]; multiset<int> mns; mns.insert(0); for(int i=0; i<N; i++){ if(lng[i]<M) dp[i]=1e9; else dp[i]=(*mns.begin())+1; mns.insert(dp[i]); if(mns.size()>M&&i>=M) mns.erase(mns.find(dp[i-M])); else if(mns.size()>M) mns.erase(0); } if(dp[N-1]>=1e6) return -1; return dp[N-1]; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 1 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 0 ms | 364 KB | Output is correct |
7 | Correct | 1 ms | 364 KB | Output is correct |
8 | Correct | 1 ms | 364 KB | Output is correct |
9 | Correct | 1 ms | 364 KB | Output is correct |
10 | Correct | 1 ms | 384 KB | Output is correct |
11 | Correct | 1 ms | 364 KB | Output is correct |
12 | Correct | 1 ms | 364 KB | Output is correct |
13 | Correct | 2 ms | 2668 KB | Output is correct |
14 | Correct | 2 ms | 2668 KB | Output is correct |
15 | Correct | 2 ms | 2668 KB | Output is correct |
16 | Correct | 3 ms | 2668 KB | Output is correct |
17 | Correct | 3 ms | 2668 KB | Output is correct |
18 | Correct | 2 ms | 2668 KB | Output is correct |
19 | Runtime error | 6 ms | 5356 KB | Execution killed with signal 11 |
20 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 1 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 0 ms | 364 KB | Output is correct |
7 | Correct | 1 ms | 364 KB | Output is correct |
8 | Correct | 1 ms | 364 KB | Output is correct |
9 | Correct | 1 ms | 364 KB | Output is correct |
10 | Correct | 1 ms | 384 KB | Output is correct |
11 | Correct | 1 ms | 364 KB | Output is correct |
12 | Correct | 1 ms | 364 KB | Output is correct |
13 | Correct | 2 ms | 2668 KB | Output is correct |
14 | Correct | 2 ms | 2668 KB | Output is correct |
15 | Correct | 2 ms | 2668 KB | Output is correct |
16 | Correct | 3 ms | 2668 KB | Output is correct |
17 | Correct | 3 ms | 2668 KB | Output is correct |
18 | Correct | 2 ms | 2668 KB | Output is correct |
19 | Runtime error | 6 ms | 5356 KB | Execution killed with signal 11 |
20 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 1 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 0 ms | 364 KB | Output is correct |
7 | Correct | 1 ms | 364 KB | Output is correct |
8 | Correct | 1 ms | 364 KB | Output is correct |
9 | Correct | 1 ms | 364 KB | Output is correct |
10 | Correct | 1 ms | 384 KB | Output is correct |
11 | Correct | 1 ms | 364 KB | Output is correct |
12 | Correct | 1 ms | 364 KB | Output is correct |
13 | Correct | 2 ms | 2668 KB | Output is correct |
14 | Correct | 2 ms | 2668 KB | Output is correct |
15 | Correct | 2 ms | 2668 KB | Output is correct |
16 | Correct | 3 ms | 2668 KB | Output is correct |
17 | Correct | 3 ms | 2668 KB | Output is correct |
18 | Correct | 2 ms | 2668 KB | Output is correct |
19 | Runtime error | 6 ms | 5356 KB | Execution killed with signal 11 |
20 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 1 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 0 ms | 364 KB | Output is correct |
7 | Correct | 1 ms | 364 KB | Output is correct |
8 | Correct | 1 ms | 364 KB | Output is correct |
9 | Correct | 1 ms | 364 KB | Output is correct |
10 | Correct | 1 ms | 384 KB | Output is correct |
11 | Correct | 1 ms | 364 KB | Output is correct |
12 | Correct | 1 ms | 364 KB | Output is correct |
13 | Correct | 2 ms | 2668 KB | Output is correct |
14 | Correct | 2 ms | 2668 KB | Output is correct |
15 | Correct | 2 ms | 2668 KB | Output is correct |
16 | Correct | 3 ms | 2668 KB | Output is correct |
17 | Correct | 3 ms | 2668 KB | Output is correct |
18 | Correct | 2 ms | 2668 KB | Output is correct |
19 | Runtime error | 6 ms | 5356 KB | Execution killed with signal 11 |
20 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | Output is correct |
2 | Correct | 1 ms | 364 KB | Output is correct |
3 | Correct | 1 ms | 364 KB | Output is correct |
4 | Correct | 1 ms | 364 KB | Output is correct |
5 | Correct | 1 ms | 364 KB | Output is correct |
6 | Correct | 0 ms | 364 KB | Output is correct |
7 | Correct | 1 ms | 364 KB | Output is correct |
8 | Correct | 1 ms | 364 KB | Output is correct |
9 | Correct | 1 ms | 364 KB | Output is correct |
10 | Correct | 1 ms | 384 KB | Output is correct |
11 | Correct | 1 ms | 364 KB | Output is correct |
12 | Correct | 1 ms | 364 KB | Output is correct |
13 | Correct | 2 ms | 2668 KB | Output is correct |
14 | Correct | 2 ms | 2668 KB | Output is correct |
15 | Correct | 2 ms | 2668 KB | Output is correct |
16 | Correct | 3 ms | 2668 KB | Output is correct |
17 | Correct | 3 ms | 2668 KB | Output is correct |
18 | Correct | 2 ms | 2668 KB | Output is correct |
19 | Runtime error | 6 ms | 5356 KB | Execution killed with signal 11 |
20 | Halted | 0 ms | 0 KB | - |