Submission #1029869

#TimeUsernameProblemLanguageResultExecution timeMemory
1029869_8_8_Painting Walls (APIO20_paint)C++17
100 / 100
149 ms38888 KiB
#include "paint.h" #include <bits/stdc++.h> using namespace std; const int N = 1e6 + 13; vector<int> v[N]; int dp[N],n,lst[N],val[N],val1[N]; int minimumInstructions(int nn, int m, int k,vector<int> C,vector<int> A,vector<vector<int>> B) { n = nn; for(int i = 0;i < m;i++){ for(int j:B[i]){ v[j].push_back(i); } } set<int> st; const int inf = 1e9; st.insert(n); for(int i = n - 1;i >= 0;i--){ bool ok = false; for(int j:v[C[i]]){ int nx = j + 1; if(j + 1==m) nx = 0; if(lst[nx] == i + 1){ val1[j] = val[nx] + 1; }else{ val1[j] = 1; } if(val1[j] >= m){ ok = true; } } for(int j:v[C[i]]){ lst[j] = i; val[j] = val1[j]; } if(ok){ auto it = st.upper_bound(i + m); if(it == st.begin()){ dp[i] = inf; }else{ it--; if(dp[*it] == inf) dp[i] = inf; else dp[i] = dp[*it] + 1; } st.insert(i); }else{ dp[i] =inf; continue; } } return (dp[0] < inf? dp[0]:-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...