Submission #984504

#	Time	Username	Problem	Language	Result	Execution time	Memory
984504		3mara	Painting Walls (APIO20_paint)	C++17	51 / 100	1575 ms	12124 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>
using namespace std;

const int N=100005;

int dp[N];
vector<int> col[N]; 

int minimumInstructions(int n, int m, int K, vector<int> v, vector<int> A, vector<vector<int>> a) {
  	for(int i=0;i<=n;i++) dp[i]=1e9;
  	for(int i=0;i<m;i++){
  		for(auto j:a[i]){
  			col[j].push_back(i);
  		}
  	}
  	dp[0]=0;
  	for(int i=0;i<=n-m;i++){
  		bool flag=1;
  		for(auto ii:col[v[i]]){
  			flag=0; int j=ii;
  			for(int cnt=0;cnt<m;cnt++){
	  			if(!binary_search(col[v[i+cnt]].begin(),col[v[i+cnt]].end(),j)) flag=1;
	  			if(flag) break;
	  			j++; j%=m;
	  		}
	  		if(!flag) break;
  		}
  		if(!flag){
  			for(int j=1;j<=m;j++) dp[i+j]=min(dp[i]+1,dp[i+j]);
  		}
  	}
  	if(dp[n]>=1e9) return -1;
  	return dp[n];
}

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