Submission #1054473

#TimeUsernameProblemLanguageResultExecution timeMemory
1054473alexander707070Painting Walls (APIO20_paint)C++14
12 / 100
46 ms30296 KiB
#include<bits/stdc++.h> #include "paint.h" #define MAXN 100007 using namespace std; int n,m,k,ans; int c[MAXN]; unordered_set<int> cols[MAXN]; vector<int> where[MAXN]; bool can[MAXN]; int to[2][MAXN]; int best[MAXN],pref[MAXN]; int li[MAXN],tim; 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]; } for(int i=1;i<=m;i++){ for(int s:B[i-1]){ cols[i].insert(s); where[s].push_back(i); } } for(int i=n;i>=1;i--){ for(int f:where[c[i]]){ if(li[f+1]!=tim)to[1-i%2][f+1]=0; if(li[1]!=tim)to[1-i%2][1]=0; if(f<m)to[i%2][f]=to[1-i%2][f+1]+1; else to[i%2][f]=to[1-i%2][1]+1; if(to[i%2][f]>=m)best[i]=max(best[i],i+m); li[f]=tim+1; } tim++; } for(int i=1;i<=n;i++){ pref[i]=max(pref[i-1],best[i]); } int pos=1; while(pos<=n){ if(pref[pos]<=pos)return -1; pos=pref[pos]; ans++; } return ans; } /* int main(){ //cout<<minimumInstructions(8, 3, 5, {3, 3, 1, 3, 4, 4, 2, 2}, {3, 2, 2}, {{0, 1, 2}, {2, 3}, {3, 4}}); cout<<minimumInstructions(5, 4, 4, {1, 0, 1, 2, 2}, {2, 1, 1, 1}, {{0, 1}, {1}, {2}, {3}}); return 0; } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...