# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
393249 | 2021-04-23T04:53:35 Z | anime | Painting Walls (APIO20_paint) | C++14 | 0 ms | 0 KB |
#include "grader.cpp" #include "paint.h" #include <bits/stdc++.h> #define pb push_back #define pii pair<int,int> #define fr first #define sc second #define OK puts("OK"); #define endi puts(""); #define ret return #define all(s) s.begin(),s.end() using namespace std; const int N = 1e5+5,INF = 1e9+7; vector <int> v[N],c; int n,m,k; bitset <2000> can[N]; int p[N],dp[20000][2000]; bool is(int l,int r){ int i,x = r-l+1; for (i=0;i<m;++i){ if (l == 0){ if (dp[r][i] == x)ret 1; } else { int y = dp[r][i]-dp[l-1][i]; if (y == x)ret 1; } } ret 0; } int minimumInstructions(int N, int M, int K,vector<int> C,vector<int> A, vector<vector<int>> B){ c = C;n=N;m=M;k=K; int i,j,ans=0; for (i=0;i<m;++i) for (int x: B[i]) can[x][i] = 1; for (i=0;i<n;++i){ if (i > 0) for (j=0;j<m;++j){ int x = j-1; x+=m; x%=m; dp[i][j] = dp[i-1][x]; } for (j=0;j<m;++j) if (can[c[i]][j] == 1) dp[i][j]++; } for (i=0;i<n-m+1;++i) p[i] = is(i,i+m-1); int pos = 0,z=1; while (pos >= 0 && pos < n && z>0){ if (p[pos] == 1){ pos +=m; ans++; z= m; } else { pos--; z--; } } if (pos < n)ans= -1; ret ans; }