Submission #1226065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226065		PanosPask	Painting Walls (APIO20_paint)	C++20	28 / 100	1595 ms	6984 KiB

paint

#include "paint.h"

#include <vector>

using namespace std;

const int INF = 1e6;

// How few instructions to paint the first i days?
vector<int> dp;

bool find(vector<int>& v, int a) {
	int p = lower_bound(v.begin(), v.end(), a) - v.begin();
	if (p == v.size()) {
		return false;
	}

	return v[p] == a;
}

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
	dp.assign(N + 1, INF);
	dp[0] = 0;

	for (int i = 0; i <= N - M; i++) {
		bool good = false;
		for (int s = 0; s < M && good == false; s++) {
			good = true;
			for (int l = 0; l < M; l++) {
				int v = (l + s) % M;
				if (find(B[v], C[i + l]) == false) {
					good = false;
					break;
				}
			}
		}

		if (good) {
			for (int j = 1; j <= M; j++) {
				dp[i + j] = min(dp[i + j], dp[i] + 1);
			}
		}
	}

	if (dp[N] == INF) {
		return -1;
	}
	return dp[N];
}

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