제출 #560802

#제출 시각아이디문제언어결과실행 시간메모리
560802HappyPacMan벽 칠하기 (APIO20_paint)C++14
100 / 100
585 ms17968 KiB
#include "paint.h" #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 2; vector<int> used[maxn]; set<pair<int,int> > st; int valid[maxn],dpv[2][maxn],dp[maxn]; int minimumInstructions(int N,int M,int K,vector<int> C,vector<int> A,vector<vector<int> > B){ for(int i=0;i<M;i++){ for(int j=0;j<A[i];j++){ used[B[i][j]].emplace_back(i); } } memset(dpv,-1,sizeof(dpv)); for(int it : used[C[N-1]]){ dpv[(N-1)&1][it] = N-1; if(dpv[(N-1)&1][it]-(N-1)+1 >= M){ valid[N-1+M-1] = true; } } for(int i=N-2;i>=0;i--){ for(int it : used[C[i]]){ if(dpv[(i+1)&1][(it+1)%M] == -1){ dpv[i&1][it] = i; }else{ dpv[i&1][it] = dpv[(i+1)&1][(it+1)%M]; } if(dpv[i&1][it]-i+1 >= M){ valid[i+M-1] = true; } } for(int it : used[C[i+1]]){ dpv[(i+1)&1][it] = -1; } } memset(dp,-1,sizeof(dp)); dp[0] = 0; st.emplace(0,0); for(int i=M;i<=N;i++){ if(valid[i-1] && !st.empty()){ dp[i] = 1+(*st.begin()).first; st.emplace(dp[i],i); } if(dp[i-M] != -1){ st.erase(st.lower_bound(make_pair(dp[i-M],i-M))); } } return dp[N]; }
#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...