Submission #294531

#	Time	Username	Problem	Language	Result	Execution time	Memory
294531		nandonathaniel	Painting Walls (APIO20_paint)	C++14	100 / 100	443 ms	498552 KiB

paint

#include "paint.h"
#include "bits/stdc++.h"
using namespace std;
const int MAXN=100005,MAXM=50005;

bool ada[MAXN];
int terakhir[MAXN];
bitset<MAXN> wrn[MAXM];
vector<int> F[MAXN],now,prv;

int minimumInstructions(
    int N, int M, int K, std::vector<int> C,
    std::vector<int> A, std::vector<std::vector<int>> B) {
    for(int i=0;i<M;i++){
    	for(auto isi : B[i]){
    		F[isi].push_back(i);
    		wrn[i][isi]=true;
		}
	}
	now.resize(M);prv.resize(M);
	for(auto isi : F[C[N-1]]){
		prv[isi]=N-1;
		if(prv[isi]>=N-1+M-1)ada[N-1]=true;
	}
	for(int i=N-2;i>=0;i--){
		for(auto isi : F[C[i]]){
			if(wrn[(isi+1)%M][C[i+1]]){
				now[isi]=prv[(isi+1)%M];
			}
			else{
				now[isi]=i;
			}
			if(now[isi]>=i+M-1)ada[i]=true;
		}
		now.swap(prv);
	}
	int lastnyala=-1;
	for(int i=0;i<N;i++){
		if(ada[i])lastnyala=i;
		terakhir[i]=lastnyala;
	}
	if(!ada[0])return -1;
	int cover=M-1,ans=1,last=0;
	while(cover!=N-1){
		int i=terakhir[cover+1];
		if(i>=last+1){
			cover=i+M-1;
			last=i;
			ans++;
		}
		else return -1;
	}
	return ans;
}

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