Submission #935179

#	Time	Username	Problem	Language	Result	Execution time	Memory
935179		MinaRagy06	Painting Walls (APIO20_paint)	C++17	28 / 100	1601 ms	59144 KiB

paint

#include <bits/stdc++.h>
#ifdef MINA
#include "grader.cpp"
#endif
#include "paint.h"
using namespace std;
#define ll long long

int minimumInstructions(int n, int m, int K, vector<int> a, vector<int> sz, vector<vector<int>> b) {
	vector<int> col[K];
	for (int i = 0; i < m; i++) {
		for (auto j : b[i]) {
			col[j].push_back(i);
		}
	}
	vector<int> diff[n];
	for (int i = 0; i < n; i++) {
		for (auto j : col[a[i]]) {
			diff[i].push_back(i - j);
		}
		sort(diff[i].begin(), diff[i].end());
	}
	int dp[n + 1]{};
	dp[n] = 0;
	for (int i = n - 1; i > n - m; i--) {
		dp[i] = 1e9;
	}
	for (int i = n - m; i >= 0; i--) {
		dp[i] = 1e9;
		bool ok = 0;
		for (auto j : col[a[i]]) {
			bool gud = 1;
			int st = i + m - j;
			for (int k = i; k < st; k++) {
				gud &= binary_search(diff[k].begin(), diff[k].end(), i - j);
			}
			for (int k = st; k < i + m; k++) {
				gud &= binary_search(diff[k].begin(), diff[k].end(), st);
			}
			ok |= gud;
		}
		if (ok) {
			for (int j = i + 1; j <= i + m; j++) {
				dp[i] = min(dp[i], dp[j] + 1);
			}
		}
	}
	if (dp[0] >= (int)1e9) return -1;
	return dp[0];
}

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