Submission #981870

#TimeUsernameProblemLanguageResultExecution timeMemory
981870AbitoPainting Walls (APIO20_paint)C++17
0 / 100
1 ms348 KiB
#include "paint.h" #include <bits/stdc++.h> #define pb push_back #define ep insert using namespace std; const int N=1e5+5; int c[N],dp[N],d[N],r[N]; int minimumInstructions( int n, int m, int k, vector<int> C, vector<int> A, vector<vector<int>> B){ for (int i=1;i<=n;i++) c[i]=C[i-1]; for (int i=1;i<=k;i++) d[i]=-1; for (int i=0;i<m;i++) for (auto u:B[i]) d[u+1]=i; for (int i=1;i<=n;i++) if (d[c[i]]==-1) return -1; r[n]=n; for (int i=n-1;i;i--){ r[i]=i; if ((d[c[i]]+1)%m==d[c[i+1]]) r[i]=r[i+1]; } for (int i=1;i<=n;i++) dp[i]=N; multiset<int> s;s.ep(0); for (int i=1;i<m;i++) s.ep(N); for (int i=n;i;i--){ if (i+m>n+1) continue; if (r[i]-i+1>=m) dp[i]=*s.begin()+1; s.erase(s.find(dp[i+m])); s.ep(dp[i]); } if (dp[1]>=N) return -1; return dp[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...