Submission #1163349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1163349		choochoo	Painting Walls (APIO20_paint)	C++20	51 / 100	415 ms	589824 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ve vector
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<ll,ll>

int n, m;

int ans(int i, ve<int>& arr) {
	if (i >= n) return 0;
	if (i - arr[i] >= m) return INT_MIN;
	return ans(arr[i]+m, arr) + 1;
}

int minimumInstructions(int N, int M, int K, std::vector<int> C, std::vector<int> A, std::vector<std::vector<int>> B) {
	ve<ve<int>> dp(N, ve<int>(M));
	ve<ve<bool>> valid(M, ve<bool>(K));
	ve<bool> seg(N);
	ve<int> best(N);
	n = N; m = M;
	for (int i=0; i<M; i++) {
		for (auto j:B[i]) {
			valid[i][j] = true;
		}
	}
	
	for (int j=0; j<M; j++) {
		if (valid[j][C[N-1]]) {dp[N-1][j] = 1;}
		else {dp[N-1][j] = -1;}
	}
	for (int i=N-2; i>=0; i--) {
		for (int j=0; j<M; j++) {
			if (valid[j][C[i]]) {
				if (dp[i+1][(j+1)%M] != -1) {
					dp[i][j] = dp[i+1][(j+1)%M] + 1;
				}
				else {dp[i][j] = 1;}
			} else {dp[i][j] = -1;}
		}
	}

	for (int i=0; i<N; i++) {
		for (int j=0; j<M; j++) {
			if (dp[i][j] >= M) {
				seg[i] = true;
				break;
			}
		}
		if (i == 0 && !seg[i]) {return -1;}
		if (seg[i]) {best[i] = i;}
		else {best[i] = best[i-1];}
	}
	
	int hi = ans(0, best);
	if (hi <= 0) return -1;
	return hi;
}

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