Submission #1201524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201524		shn	Painting Walls (APIO20_paint)	C++20	0 / 100	0 ms	324 KiB

paint

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

int minimumInstructions(int N, int M, int K, vector<int> C,vector<int> A,vector<vector<int>> B){
	bool ok[M][K];
	vector < int > g[K] , d[N];
	for(int i = 0; i < M; i++){
		for(int j = 0; j < K; j++) ok[i][j] = 0;
		for(int j = 0; j < A[i]; j++){
			ok[i][B[i][j]] = 1;
			g[B[i][j]].push_back(i);
		}
	}
	vector < pair < int , int > > v;
	map < int , int > last[2];
	for(int i = 0; i <= N - M; i++){
		last[i & 1].clear();
		for(int it : g[C[i]]){
			int prev = it - 1;
			if(prev == -1) prev = M - 1;
			last[i & 1][it] = last[(i & 1) ^ 1][prev];
			if(last[i & 1][it] + M - 1 <= i) d[i - M + 1].push_back(i);
		}
	}
	int dst[N];
	for(int i = 1; i < N; i++){
		dst[i] = 1e9;
		d[i].push_back(i - 1);
	}
	dst[0] = 0;
	queue < int > q;
	q.push(0);
	while(q.size() > 0){
		int v = q.front();
		q.pop();
		for(int to : d[v]){
			if(to == v - 1){
				if(dst[to] > dst[v]){
					dst[to] = dst[v];
					q.push(to);
				}
			}
			else{
				if(dst[to] > dst[v] + 1){
					dst[to] = dst[v] + 1;
					q.push(to);
				}
			}
		}
	}
	if(dst[N - 1] == 1e9) return -1;
	return dst[N - 1];
}

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