Submission #719331

#TimeUsernameProblemLanguageResultExecution timeMemory
719331Radin_Zahedi2Painting Walls (APIO20_paint)C++17
100 / 100
997 ms14940 KiB
#include "paint.h" #include<bits/stdc++.h> //#include <vector> using namespace std; #define pb push_back #define mp make_pair #define fi first #define se second #define sz(x) (int)x.size() #define endl '\n' int minimumInstructions( int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B) { vector<int> have[K]; for (int i = 0; i < M; i++) { for (int j = 0; j < A[i]; j++) { have[B[i][j]].pb(i); } } bool can[N]; fill(can + 0, can + N, false); int best[M]; fill(best + 0, best + M, 0); vector<int> pre; for (int i = 0; i < N; i++) { vector<int> now; for (auto x : have[C[i]]) { int pre = x - 1; if (pre == -1) { pre = M - 1; } now.pb(best[pre] + 1); } for (auto x : now) { if (x >= M) { can[i] = true; } } for (auto x : pre) { best[x] = 0; } pre.clear(); for (int j = 0; j < sz(have[C[i]]); j++) { best[have[C[i]][j]] = now[j]; pre.pb(have[C[i]][j]); } } int dp[N]; deque<pair<int, int>> q; q.push_back(mp(-1, 0)); for (int i = 0; i < N; i++) { if (!can[i]) { dp[i] = -1; continue; } while (!q.empty()) { if (i - q.front().fi <= M) { break; } q.pop_front(); } if (q.empty()) { dp[i] = -1; continue; } dp[i] = q.front().se + 1; while (!q.empty()) { if (q.back().se < dp[i]) { break; } q.pop_back(); } q.push_back(mp(i, dp[i])); } return dp[N - 1]; }
#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...