Submission #1226080

#TimeUsernameProblemLanguageResultExecution timeMemory
1226080Godgift42Painting Walls (APIO20_paint)C++20
28 / 100
318 ms589824 KiB
#include "paint.h" #include <vector> #include <bits/stdc++.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) { int n=N; int m=M; int k=K; vector<int>c=C; vector<int>a=A; vector<vector<int>>b=B; vector<unordered_set<int>> cont(m); for(int i=0;i<m;i++){ for(auto j:b[i])cont[i].insert(j); } vector<vector<int>> dp(2*n,vector<int>(2*n,-1)); for(int i=0;i<2*n-m+1;i++){ for(int j=0;j<m;j++){ bool val=true; for(int o=0;o<m;o++){ if(cont[(j+o)%m].count(c[(i+o)%n])==0){ val=false; break; } } if(val)dp[i][i+m-1]=1; } } for(int i=m;i<n;i++){ for(int j=0;j<2*n-i;j++){ if(dp[j][j+m-1]==-1)continue; for(int o=j+1;o<min(j+m+1,j+i-m+2);o++){ if(dp[o][i+j]!=-1){ if(dp[j][i+j]==-1)dp[j][i+j]=dp[o][i+j]+1; else dp[j][i+j]=min(dp[j][i+j],dp[o][i+j]+1); } } int ed=i+j; if(dp[ed+1-m][ed]==-1)continue; for(int o=max(j+m-1,ed-m);o<ed;o++){ if(dp[j][o]!=-1){ if(dp[j][i+j]==-1)dp[j][i+j]=dp[j][o]+1; else dp[j][i+j]=min(dp[j][i+j],dp[j][o]+1); } } } } int ans=-1; for(int i=0;i<n;i++){ if(dp[i][i+n-1]!=-1){ if(ans==-1)ans=dp[i][i+n-1]; else ans=min(ans,dp[i][i+n-1]); } } return ans; }
#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...