Submission #576439

#	Time	Username	Problem	Language	Result	Execution time	Memory
576439		pooyashams	Painting Walls (APIO20_paint)	C++14	100 / 100	355 ms	13388 KiB

paint

#include "paint.h"
#include <iostream>

#include <vector>

using namespace std;

const int maxn = 1e5+10;

vector<int> wrks[maxn];
int dp[2][maxn];
bool cann[maxn];
int lcnn[maxn];

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 c: B[i])
			wrks[c].push_back(i);
	bool f = !(N&1);
	for(int j: wrks[C[N-1]])
	{
		dp[f][j] = 1;
		if(dp[f][j] == M)
			cann[N-1] = true;
	}
	for(int i = N-2; i >= 0; i--)
	{
		f = !f;
		int p = 0;
		int cn = C[i+1];
		int cs = wrks[cn].size();
		for(int j: wrks[C[i]])
		{
			dp[f][j] = 1;
			while(p < cs and wrks[cn][p] <= j)
				p++;
			if(j == M-1 and !wrks[cn].empty() and wrks[cn][0] == 0)
				dp[f][j] += dp[!f][0];
			else if(p < cs and wrks[cn][p] == j+1)
				dp[f][j] += dp[!f][j+1];
			dp[f][j] = min(M, dp[f][j]);
			if(dp[f][j] == M)
				cann[i] = true;
		}
	}
	//for(int i = 0; i < N; i++) cerr << cann[i]; cerr << endl;
	int lc = -1;
	for(int i = 0; i < N; i++)
	{
		if(cann[i])
			lc = i;
		lcnn[i] = lc;
	}
	int p = 0;
	int t = 0;
	while(p < N)
	{
		int r = lcnn[p];
		if(r == -1 or r+M == p)
			return -1;
		p = r+M;
		t++;
	}
	return t;
}

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