Submission #981880

#TimeUsernameProblemLanguageResultExecution timeMemory
981880AbitoPainting Walls (APIO20_paint)C++17
12 / 100
44 ms10996 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],p[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]+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; for (int i=1;i<n;i++) p[i]=p[i-1]+bool((d[c[i]]+1)%m==d[c[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 (p[i+m-2]-p[i-1]==m-1) 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...