제출 #684612

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
684612		thiago_bastos	벽 칠하기 (APIO20_paint)	C++17	100 / 100	484 ms	15632 KiB

paint

#include "paint.h"

#include <bits/stdc++.h>

using namespace std;

#define INF 1000000000
#define pb push_back
#define rall(x) x.rbegin(),x.rend()

using ii = pair<int, int>;

int minimumInstructions(int N, int M, int K,vector<int> C,vector<int> A,vector<std::vector<int>> B) {
	
	vector<vector<int>> match(K);
	vector<int> time_(M, N), cur(M, 0), tcur(M);

	for(int i = 0; i < M; ++i)
		for(int c : B[i])
			match[c].pb(i);

	vector<int> st(2 * N + 2, INF);

	auto query = [&](int l, int r) {
		int ans = INF;
		l += N, r += N;
		for(; l <= r; l /= 2, r /= 2) {
			if(l & 1) ans = min(ans, st[l++]);
			if(~r & 1) ans = min(ans, st[r--]);
		}
		return ans;
	};

	auto upd = [&](int k, int x) {
		k += N;
		st[k] = x;
		for(k /= 2; k; k /= 2) st[k] = min(st[2 * k], st[2 * k + 1]);
	};

	upd(N, 0);

	int dp = 0;

	for(int i = N - 1; i >= 0; --i) {
		int jump = 0;

		for(int j : match[C[i]]) {
			int k = j + 1;
			if(k >= M) k -= M;
			if(time_[k] > i + 1) cur[k] = 0;
			cur[k] = min(cur[k], M - 1);
			tcur[j] = 1 + cur[k];
			jump = max(jump, tcur[j]);
		}
		
		for(int j : match[C[i]]) time_[j] = i;

		swap(tcur, cur);

		if(jump == M || jump >= N - i) {
			dp = query(i + 1, min(N, i + jump)) + 1;
			upd(i, dp);
		} else
			dp = INF;
	}
			
	return dp > N ? -1 : dp;
}

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