제출 #500904

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
500904		sidon	벽 칠하기 (APIO20_paint)	C++17	63 / 100	1564 ms	14052 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[2];
	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();

		toR[i & 1].clear();

		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);
		}
	}

	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: 0 / 37