Submission #500902

#	Time	Username	Problem	Language	Result	Execution time	Memory
500902		sidon	Painting Walls (APIO20_paint)	C++17	40 / 100	1394 ms	524292 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) {
	map<int, int> toR[N+1];
	deque<int> q = {N};
	vector<int> cand[K], dp(N+1, INF);
	dp[N] = 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][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);
		}
	}

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

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