Submission #1058351

#TimeUsernameProblemLanguageResultExecution timeMemory
1058351mispertionPainting Walls (APIO20_paint)C++17
0 / 100
1 ms2652 KiB
#include "paint.h" #include <bits/stdc++.h> #include <vector> using namespace std; const int N = 1e5 + 10; #define sz(x) (int)x.size() #define pb push_back int n, m, k, ok[N]; vector<int> c, a; vector<vector<int>> pos, b; vector<int> dp[N]; int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, vector<vector<int>> B) { n = N; m = M; k = K; c = C; a = A; b = B; pos.resize(k); for(int i = 0; i < m; i++){ for(auto e : b[i]) pos[e].pb(i); } for(int i = 0; i < n; i++){ dp[i].assign(sz(pos[c[i]]), 1); if(sz(dp[i]) == 0) return -1; } if(k == 1) return n; for(int i = n - 2; i >= 0; i--){ int ru = 0; for(int lu = 0; lu < sz(dp[i]); lu++){ while(ru < sz(dp[i + 1]) && pos[c[i + 1]][ru] <= pos[c[i]][lu]) ru++; if(ru == sz(dp[i + 1]) || pos[c[i]][lu] + 1 < pos[c[i + 1]][ru]) continue; dp[i][lu] = dp[i + 1][ru] + 1; } if(pos[c[i]][sz(dp[i]) - 1] == m - 1 && pos[c[i + 1]][0] == 0) dp[i][sz(dp[i]) - 1] = dp[i + 1][0] + 1; for(auto e : dp[i]){ if(e >= m) ok[i] = 1; } } int ans = 0, r = 0; while(r < n){ int nr = -1; for(int l = 0; l < m; l++){ if(r - l < 0) break; if(ok[r - l]){ nr = r - l + m; break; } } if(nr == -1) return -1; ans++; r = nr; } 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...