Submission #553299

#	Time	Username	Problem	Language	Result	Execution time	Memory
553299		FatihSolak	벽 칠하기 (APIO20_paint)	C++17	100 / 100	652 ms	290388 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#define N 100005
#define K 705
using namespace std;
vector<int> col[N];
int dp[N][K];
int ok[N];
int minimumInstructions(int n, int m, int k, vector<int> c,vector<int> a, vector<vector<int>> b) {
	for(int i = 0;i<m;i++){
		for(int j = 0;j<a[i];j++){
			col[b[i][j]].push_back(i);
		}
	}
	for(int i = 0;i<n;i++){
		if(col[c[i]].size() == 0)
			return -1;
	}
	/*
	for(int i = 0;i<k;i++){
		for(auto u:col[i]){
			cout << u << " ";
		}
		cout << endl;
	}*/
	for(int i = 0;i<col[c[0]].size();i++){
		dp[0][i] = 1; 
		if(dp[0][i] == m)
			ok[0 - m + 1] = 1;
	}
	for(int i = 1;i<n;i++){ 
		int pt = 0;
		for(int j = 0;j<col[c[i]].size();j++){
			dp[i][j] = 1;
			while(pt + 1 < col[c[i-1]].size() &&  col[c[i-1]][pt] + 1 < col[c[i]][j]){
				pt++;
			}
			//cout << "hey" << pt << endl;
			if(col[c[i-1]][pt] + 1 == col[c[i]][j]){
				dp[i][j] = max(dp[i][j],min(m, dp[i-1][pt]+1));
			}
			if(col[c[i]][j] == 0 && col[c[i-1]].back() == m-1){
				dp[i][j] = max(dp[i][j],min(m, dp[i-1][col[c[i-1]].size()-1]+1));
			}
			//cout << dp[i][j] << " ";
			if(dp[i][j] == m)
				ok[i - m  +1] = 1;
		}
		//cout << endl;
	}
	/*
	for(int i = 0;i<n;i++){
		cout << ok[i] << " ";
	}
	cout << endl;*/
	int cnt = 0;
	int last = -1;
	int maxi = 0;
	while(maxi < n){
		int val = maxi;
		for(int i = last+1;i<=maxi;i++){
			if(ok[i]){
				val = max(val,i + m);
			}
		}
		if(val == maxi){
			return -1;
		}
		cnt++;
		last = maxi;
		maxi = val;
	}
	return cnt;
}

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:26:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for(int i = 0;i<col[c[0]].size();i++){
      |                ~^~~~~~~~~~~~~~~~~
paint.cpp:33:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   for(int j = 0;j<col[c[i]].size();j++){
      |                 ~^~~~~~~~~~~~~~~~~
paint.cpp:35:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |    while(pt + 1 < col[c[i-1]].size() &&  col[c[i-1]][pt] + 1 < col[c[i]][j]){
      |          ~~~~~~~^~~~~~~~~~~~~~~~~~~~

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