Submission #733233

#TimeUsernameProblemLanguageResultExecution timeMemory
733233bin9638Painting Walls (APIO20_paint)C++17
100 / 100
1480 ms15748 KiB
#include <bits/stdc++.h> #ifndef SKY #include "paint.h" #endif // SKY using namespace std; #define N 100010 #define ll long long #define fs first #define sc second #define ii pair<int,int> #define pb push_back int mp[2][N]; int n,m,k,color[N],dp[N]; vector<int>lis[N]; int minimumInstructions(int NNN, int MMM, int KKK, vector<int> CCC,vector<int> AAA, vector<vector<int>> BBB) { n=NNN; m=MMM; k=KKK; for(int i=0;i<n;i++) color[i]=CCC[i]; for(int i=0;i<m;i++) for(auto u:BBB[i]) lis[u].pb(i); if(m==1) { for(int i=0;i<n;i++) if(lis[color[i]].empty()) return -1; return n; } for(int i=n-1;i>=0;i--) { memset(mp[(i&1)],0,sizeof(mp[(i&1)])); for(auto u:lis[color[i]]) if(mp[(i+1)&1][(u+1)%m]!=0) mp[(i&1)][u]=min(m,mp[(i+1)&1][(u+1)%m]+1); else mp[(i&1)][u]=1; for(auto u:lis[color[i]]) if(mp[(i&1)][u]==m) dp[i]=1; } if(dp[0]==0) return -1; int vt=0,res=0,x=0; while(vt<n) { if(x+m-1<vt) return -1; int new_vt=x+m; for(int i=vt+1;i<=new_vt;i++) if(dp[i]==1) x=max(x,i); vt=new_vt; res++; } return res; } #ifdef SKY int main() { freopen("A.inp","r",stdin); freopen("A.out","w",stdout); ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int n,m,k; cin>>n>>m>>k; vector<int>C(n); for(int i=0;i<n;i++) cin>>C[i]; vector<int>A(m); vector<vector<int>>B(m); for(int i=0;i<m;i++) { cin>>A[i]; B[i].resize(A[i]); } for(int i=0;i<m;i++) { for(int j=0;j<A[i];j++) cin>>B[i][j]; } cout<<minimumInstructions(n,m,k,C,A,B); return 0; } #endif
#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...