Submission #294916

#	Time	Username	Problem	Language	Result	Execution time	Memory
294916		Berted	Painting Walls (APIO20_paint)	C++14	100 / 100	766 ms	268036 KiB

paint

#include "paint.h"

#include <vector>
#include <algorithm>
#include <iostream>
#define vi vector<int>
using namespace std;

const int INF = 1e9;

vi clr[100001];
vi pos[100001];
int dp[100001][633];
bool f[100001];

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) 
{
	for (int i = 0; i < N; i++) {clr[C[i]].push_back(i);}
	for (int i = 0; i < M; i++)
	{
		for (int j = 0; j < A[i]; j++)
		{
			pos[B[i][j]].push_back(i);
		}
	}
	for (int i = 0; i < K; i++) 
	{
		sort(pos[i].begin(), pos[i].end());
		pos[i].resize(unique(pos[i].begin(), pos[i].end()) - pos[i].begin());
		for (int j = 0; j < clr[i].size(); j++)
		{
			for (int k = 0; k < pos[i].size(); k++) {dp[clr[i][j]][k] = 1;}
		}
	}

	if (M == 1) {f[0] = 1;}
	
	for (int i = 1; i < N; i++)
	{
		int k = 0; int pi = C[i - 1], ci = C[i];
		for (int j = 0; j < pos[ci].size(); j++)
		{
			if (j && pos[ci][j - 1] == 0) {k = 0;}
			for (; k < pos[pi].size() && pos[pi][k] < (pos[ci][j] + M - 1) % M; k++); 
			if (k < pos[pi].size() && pos[pi][k] == (pos[ci][j] + M - 1) % M)
			{
				dp[i][j] = max(dp[i][j], dp[i - 1][k] + 1);
			}
			if (dp[i][j] >= M) {f[i] = 1;}
		}
	}

	vector<int> allow;
	for (int i = 0; i < N; i++)
	{
		if (f[i]) 
		{
			// cout << i << " is allowed\n";
			allow.push_back(i);
		}	
	}
	int ret = INF;
	if (f[M - 1])
	{
		int cur = M - 1, cnt = 1;
		while (cur < N - 1)
		{
			auto it = upper_bound(allow.begin(), allow.end(), min(N - 1, cur + M));
			it = prev(it);
			if (*it != cur) {cnt++; cur = *it;} 
			else {break;}
		}
		if (cur == N - 1) {ret = min(ret, cnt);}
	}
	if (ret == INF) return -1;
	else return ret;
}

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:30:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   for (int j = 0; j < clr[i].size(); j++)
      |                   ~~^~~~~~~~~~~~~~~
paint.cpp:32:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |    for (int k = 0; k < pos[i].size(); k++) {dp[clr[i][j]][k] = 1;}
      |                    ~~^~~~~~~~~~~~~~~
paint.cpp:41:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |   for (int j = 0; j < pos[ci].size(); j++)
      |                   ~~^~~~~~~~~~~~~~~~
paint.cpp:44:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |    for (; k < pos[pi].size() && pos[pi][k] < (pos[ci][j] + M - 1) % M; k++);
      |           ~~^~~~~~~~~~~~~~~~
paint.cpp:45:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |    if (k < pos[pi].size() && pos[pi][k] == (pos[ci][j] + M - 1) % M)
      |        ~~^~~~~~~~~~~~~~~~

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