#include "paint.h"
#include <bits/stdc++.h>
#define pb push_back
#define ep insert
using namespace std;
const int NN=1e5+5;
int n,m,k,p[NN],c[NN],dp[NN];
set<int> adj[NN];
vector<int> v[NN];
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++) c[i]=C[i-1]+1;
for (int i=1;i<=m;i++){
for (auto u:B[i-1]) adj[i].ep(u+1),v[u+1].pb(i-1);
}
for (int i=1;i<n;i++){
if (v[c[i]].empty() || v[c[i+1]].empty()) continue;
p[i]=p[i-1]+bool((v[c[i]][0]+1)%m==v[c[i+1]][0]);
}
multiset<int> s;
for (int i=1;i<=n-m+1;i++) dp[i]=10*n;
for (int i=1;i<=m;i++) s.ep(0);
for (int i=n-m+1;i;i--){
bool ok=(p[i+m-2]-p[i-1]==m-1);
if (ok) dp[i]=*s.begin()+1;
s.ep(dp[i]);
s.erase(dp[i+m]);
}
return dp[1];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
7260 KB |
Output is correct |
2 |
Correct |
4 ms |
7492 KB |
Output is correct |
3 |
Incorrect |
2 ms |
7260 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
7260 KB |
Output is correct |
2 |
Correct |
4 ms |
7492 KB |
Output is correct |
3 |
Incorrect |
2 ms |
7260 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
7260 KB |
Output is correct |
2 |
Correct |
4 ms |
7492 KB |
Output is correct |
3 |
Incorrect |
2 ms |
7260 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
7260 KB |
Output is correct |
2 |
Correct |
4 ms |
7492 KB |
Output is correct |
3 |
Incorrect |
2 ms |
7260 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
7260 KB |
Output is correct |
2 |
Correct |
4 ms |
7492 KB |
Output is correct |
3 |
Incorrect |
2 ms |
7260 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |