Submission #1200946

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200946		dibamboo23	Painting Walls (APIO20_paint)	C++20	100 / 100	369 ms	263464 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>

#define F first
#define S second
#define ll long long
#define sz size()

using namespace std;

const int N=1e5+3;

int pref[N][633];
int dp[N],mx[N];
vector<int>pos[N];
int cnt_of[N];

int minimumInstructions(
    int N, int M, int K, std::vector<int> C,
    std::vector<int> A, std::vector<std::vector<int>> B) {
    	ios_base::sync_with_stdio(0);cin.tie(0);
    	for(int i=0;i<M;i++){
    		for(int j=0;j<A[i];j++){
    			pos[B[i][j]].push_back(i);
    		}
    	}
    	for(int i=0;i<N;i++){
    		mx[i]=0;
    		if(i==0||pos[C[i-1]].empty()){
    			for(int j=0;j<(int)pos[C[i]].sz;j++){
    				pref[i][j]=1;
    				mx[i]=1;
    			}
    			continue;
    		}
    		int k=0;
    		for(int j=0;j<(int)pos[C[i]].sz;j++){
    			pref[i][j]=1;
    			int need=(pos[C[i]][j]-1+M)%M;
    			if(need==M-1){
    				if(pos[C[i-1]].back()==need){
    					pref[i][j]=pref[i-1][(int)pos[C[i-1]].sz-1]+1;
    					mx[i]=max(mx[i],pref[i][j]);
    				}
    				continue;
    			}
    			while(k<(int)pos[C[i-1]].sz&&pos[C[i-1]][k]<need)k++;
    			if(k==(int)pos[C[i-1]].sz||pos[C[i-1]][k]!=need)continue;
    			pref[i][j]=pref[i-1][k]+1;
    			mx[i]=max(mx[i],pref[i][j]);
    		}
    	}
    	multiset<int>st;
    	st.insert(0);
    	for(int i=0;i<M-1;i++){
    		dp[i]=1e9;
    		st.insert(dp[i]);
    	}
    	for(int i=M-1;i<N;i++){
    		dp[i]=1e9;
    		if(mx[i]>=M){
    			// cout<<*st.begin()<<"\n";
    			dp[i]=min(*st.begin()+1,dp[i]);
    		}
    		if(i-M==-1)st.erase(st.begin());
    		else st.erase(st.find(dp[i-M]));
    		st.insert(dp[i]);
    	}
    	// cout<<"mx :\n";
    	// for(int i=0;i<N;i++){
    		// // cout<<i<<": "<<dp[i]<<"\n";
    		// cout<<i<<": "<<mx[i]<<"\n";
    	// }
    	// cout<<"dp :\n";
    	// for(int i=0;i<N;i++){
    		// cout<<i<<": "<<dp[i]<<"\n";
    		// // cout<<i<<": "<<mx[i]<<"\n";
    	// }
    	return (dp[N-1]>=1e9?-1:dp[N-1]);
}

// int main() {
  // int N, M, K;
  // assert(3 == scanf("%d %d %d", &N, &M, &K));
//   
  // std::vector<int> C(N);
  // for (int i = 0; i < N; ++i) {
    // assert(1 == scanf("%d", &C[i]));
  // }
// 
  // std::vector<int> A(M);
  // std::vector<std::vector<int>> B(M);
  // for (int i = 0; i < M; ++i) {
    // assert(1 == scanf("%d", &A[i]));
    // B[i].resize(A[i]);
    // for (int j = 0; j < A[i]; ++j) {
      // assert(1 == scanf("%d", &B[i][j]));
    // }
  // }
// 
  // int minimum_instructions = minimumInstructions(N, M, K, C, A, B);
  // printf("%d\n", minimum_instructions);
//   
  // return 0;
// }
// 

• Subtask 1: 12 / 12
• Subtask 2: 15 / 15
• Subtask 3: 13 / 13
• Subtask 4: 23 / 23
• Subtask 5: 37 / 37