Submission #1202855

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202855		ezzzay	Painting Walls (APIO20_paint)	C++20	28 / 100	1595 ms	25480 KiB

paint

#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define ll long long
int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B ) {
	vector<int>dp(N+2);
	for(int i=0;i<=N;i++){
		dp[i]=1e9;
	}
	deque<int>q;
	for(int i=0;i<M;i++)q.pb(i);
	dp[0]=0;
	vector< vector< bool >  > mp ( M+2, vector<bool> (K+5));
	for(int i=0;i<M;i++){
		for(auto x:B[i])mp[i][x]=1;
	}
	for(int i=M;i<=N;i++){
		for(int j=0;j<=M;j++){ 
			bool u=1;
			for(int k=0;k<M;k++){
				if( mp[q[k]] [C[i-(M-k)]] ==0){
					u=0;
				}
			}
			if(u){
				dp[i]=min(dp[i],dp[i-M]+1);
				for(int k=0;k<M;k++){
					dp[i-k]=min(dp[i-k],dp[i]);
				}
				for(int i=0;i<M;i++)q.pop_back();
				for(int i=0;i<M;i++)q.pb(i);
				break;
			}
			q.pb(q.front());
			q.pop_front();
		}
	}
	if(dp[N]==1e9)return -1;
	else return dp[N];
}

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