Submission #1225933

#TimeUsernameProblemLanguageResultExecution timeMemory
1225933KALARRYPainting Walls (APIO20_paint)C++20
0 / 100
6 ms14408 KiB
//chockolateman #include<bits/stdc++.h> using namespace std; int n,m,dp[100005],c[100005],is_end[100005]; map<int,int> my_ord[100005]; map<int,bool> likes[100005]; vector<int> f[100005]; vector<int> max_ends[100005]; void calc() { for(int i = 1 ; i <= n ; i++) { max_ends[i] = f[c[i]]; for(int j = 0 ; j < max_ends[i].size() ; j++) max_ends[i][j] = 1; if(m==1) is_end[i] = true; } for(int i = 2 ; i <= n ; i++) { for(int j = 0 ; j < max_ends[i].size() ; j++) { int x = f[c[i]][j]; int prev = x-1; if(x==0) prev = m-1; if(!likes[prev][c[i-1]]) continue; int check = max_ends[i-1][my_ord[prev][c[i-1]]]; max_ends[i][j] = min(m,check + 1); if(max_ends[i][j]==m) is_end[i] = true; } } } int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B) { n = N; m = M; for(int i = N ; i >= 1 ; i--) //make it 1-indexed c[i] = C[i-1]; for(int j = 0 ; j < M ; j++) for(int s = 0 ; s < A[j] ; s++) { int x = B[j][s]; likes[j][x] = true; f[x].push_back(j); my_ord[j][x] = f[x].size() - 1; } calc(); dp[0] = 0; deque<int> avail; avail.push_back(0); for(int i = 1 ; i <= N ; i++) { dp[i] = -1; if(avail.empty()) continue; if(i >= M+1 && avail.front() == dp[i-M-1]) avail.pop_front(); if(!is_end[i]) continue; dp[i] = avail.front() + 1; while(avail.back() > dp[i]) avail.pop_back(); avail.push_back(dp[i]); } 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...