Submission #500907

#	Time	Username	Problem	Language	Result	Execution time	Memory
500907		sidon	Painting Walls (APIO20_paint)	C++17	100 / 100	510 ms	15008 KiB

paint

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

const int INF = 2e9;

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
	int toR[2][M];
	deque<int> q = {N};
	vector<int> cand[K], dp(N+1, INF);
	dp[N] = 0;

	for(int i : {0, 1})
		fill(toR[i], toR[i] + M, 0);

	for(int i = 0; i < M; i++)
		for(int &j : B[i]) 
			cand[j].push_back(i);

	for(int i = N; --i >= 0; ) {
		if(!empty(q) && q.front() > i + M) q.pop_front();

		bool ok = 0;

		for(int j : cand[C[i]]) 
			if((toR[i & 1][j] = 1 + toR[!(i & 1)][(j + 1) % M]) >= M)
				ok = 1;

		if(ok && !empty(q)) {
			dp[i] = 1 + dp[q.front()];
			while(!empty(q) && dp[i] <= dp[q.back()])
				q.pop_back();
			q.push_back(i);
		}

		if(i + 1 < N) 
			for(int j : cand[C[i+1]])
				toR[!(i & 1)][j] = 0;
	}

	return dp[0] == INF ? -1 : dp[0];
}

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