Submission #1029864

#TimeUsernameProblemLanguageResultExecution timeMemory
1029864_8_8_Painting Walls (APIO20_paint)C++17
0 / 100
1578 ms35892 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]; 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){ val[j] = val[nx] + 1; }else{ val[j] = 1; } if(val[j] >= m){ ok = true; } lst[j] = i; } if(ok){ dp[i] = inf; for(int j = i + 1;j <= min(n,i + m);j++){ if(dp[j] != inf){ dp[i] = min(dp[i],dp[j] + 1); } } }else{ dp[i] =inf; continue; } // auto it = st.upper_bound(i + m); // if(it == st.begin()){ // st.erase(i); // dp[i] = inf;continue; // } // it--; // dp[i] = dp[*it] + 1; } 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...