Submission #367178

#TimeUsernameProblemLanguageResultExecution timeMemory
367178wiwihoPainting Walls (APIO20_paint)C++14
40 / 100
1283 ms524288 KiB
#include "paint.h" #include <bits/stdc++.h> #include <bits/extc++.h> #define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define iter(a) a.begin(), a.end() #define riter(a) a.rbegin(), a.rend() #define lsort(a) sort(iter(a)) #define gsort(a) sort(riter(a)) #define pb(a) push_back(a) #define eb(a) emplace_back(a) #define pf(a) push_front(a) #define ef(a) emplace_front(a) #define pob pop_back() #define pof pop_front() #define mp(a, b) make_pair(a, b) #define F first #define S second #define mt make_tuple #define gt(t, i) get<i>(t) #define iceil(a, b) (((a) + (b) - 1) / (b)) #define tomax(a, b) ((a) = max((a), (b))) #define tomin(a, b) ((a) = min((a), (b))) #define topos(a) ((a) = (((a) % MOD + MOD) % MOD)) #define uni(a) a.resize(unique(iter(a)) - a.begin()) #define printv(a, b) {bool pvaspace=false; \ for(auto pva : a){ \ if(pvaspace) b << " "; pvaspace=true;\ b << pva;\ }\ b << "\n";} using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef unsigned long long ull; typedef long double ld; using pii = pair<int, int>; using pll = pair<ll, ll>; using pdd = pair<ld, ld>; using tiii = tuple<int, int, int>; const ll MOD = 1000000007; const ll MAX = 2147483647; template<typename A, typename B> ostream &operator<<(ostream &o, pair<A, B> p){ return o << '(' << p.F << ',' << p.S << ')'; } int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int>> b){ vector<vector<int>> ok(k); for(int i = 0; i < m; i++){ for(int j : b[i]) ok[j].eb(i); } vector<unordered_map<int, int>> dp(n + 1); for(int i = n - 1; i >= 0; i--){ for(int j : ok[c[i]]){ dp[i][j] = max(dp[i][j], dp[i + 1][(j + 1) % m] + 1); } // cerr << i << " "; // printv(dp[i], cerr); } deque<pii> dq; dq.eb(mp(-m, 0)); for(int i = 0; i < n; i++){ int mx = 0; for(auto j : dp[i]) mx = max(mx, j.S); if(mx < m) continue; while(!dq.empty() && dq.front().F < i - m) dq.pof; if(dq.empty()) break; int t = dq.front().S + 1; while(!dq.empty() && dq.back().S >= t) dq.pob; dq.eb(mp(i, t)); // cerr << i << " "; // printv(dq, cerr); } while(!dq.empty() && dq.front().F < n - m) dq.pof; if(dq.empty()) return -1; else return dq.front().S; }
#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...