Submission #996486

#TimeUsernameProblemLanguageResultExecution timeMemory
996486Dan4LifePainting Walls (APIO20_paint)C++17
0 / 100
5 ms40540 KiB
#include "paint.h" #include <bits/stdc++.h> using namespace std; #define all(a) begin(a),end(a) #define sz(a) (int)a.size() #define pb push_back const int mxN = (int)2e4+10; const int mxM = (int)2e3+10; int n, m, k; bool work[mxN]; vector<int> c, a; set<int> b[mxN]; bool has[mxM][mxN]; //has[x][y] = if contractor x contains the color used in cell y bool check(int i){ for(int x = 0; x < m; x++){ if(i+m-1-x<0){ if(has[m-1][i+m-1]) return true; } else if(x and has[m-1][i+m-1-x] and has[x-1][i+m-1]) return true; } return false; } 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(auto u : C) c.pb(u); for(auto u : A) a.pb(u); for(int i = 0; i < m; i++) for(auto u : B[i]) b[i].insert(u); memset(has,0,sizeof(has)); for(int i = 0; i < m; i++) for(int j = 0; j < n; j++) has[i][j] = b[i].count(c[j]); for(int i = 1; i < m; i++) for(int j = 1; j < n; j++) has[i][j] &= has[i-1][j-1]; memset(work,0,sizeof(work)); for(int i = 0; i <= n-m; i++) work[i] = check(i); if(!work[0] or !work[n-m]) return -1; int tot = 1; for(int i = 0; i < n-m;){ int j; for(j = i+m; j>=i; j--) if(work[j]) break; if(j==i) return -1; tot++; i = j; } return tot; }
#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...