Submission #965907

#	Time	Username	Problem	Language	Result	Execution time	Memory
965907		Darren0724	Painting Walls (APIO20_paint)	C++17	100 / 100	1208 ms	30548 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
int minimumInstructions(int N, int M, int K, vector<int> C,vector<int> A, vector<vector<int>> B) {
  	vector<int> dp(N+1,INF);
	vector<unordered_set<int>> s(K);
	for(int i=0;i<M;i++){
		for(int j:B[i]){
			s[j].insert(i);
		}
	}
	int can=0;
	vector<int> cnt(M);
	auto add=[&](int place,int x)->void {
		for(int j1:s[C[place]]){
			int j=((j1-place)%M+M)%M;
			can-=(cnt[j]==M);
			cnt[j]+=x;
			can+=(cnt[j]==M);
		}
	};
	auto check=[&](int st,int now)->int {
		for(int i=st;i<st+M;i++){
			if(!s[C[i]].count(now))return 0;
			now++;
			now%=M;
		}
		return 1;
	};	
	deque<int> d;
	d.push_back(0);
	dp[0]=0;
	for(int i=0;i<M-1;i++){
		add(i,1);
	}
	for(int i=M;i<=N;i++){
		add(i-1,1);

		/*for(int j:cnt){
			cout<<j<<' ';
		}
		cout<<endl;*/
		while(d.size()&&d.front()<i-M){
			d.pop_front();
		}
		if(can){
			dp[i]=dp[d.front()]+1;
		}
		while(d.size()&&dp[d.back()]>dp[i]){
			d.pop_back();
		}
		d.push_back(i);
		add(i-M,-1);
	}
	/*for(int i=1;i<=N;i++){
		cout<<dp[i]<<' ';
	}
	cout<<endl;*/
	return (dp[N]>=INF?-1:dp[N]);

	return 0;
}

Compilation message (stderr)

paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:23:7: warning: variable 'check' set but not used [-Wunused-but-set-variable]
   23 |  auto check=[&](int st,int now)->int {
      |       ^~~~~

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