Submission #965689

#	Time	Username	Problem	Language	Result	Execution time	Memory
965689		Gromp15	Painting Walls (APIO20_paint)	C++17	28 / 100	1544 ms	13148 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

const int INF = 1e9;
int minimumInstructions(
    int n, int m, int k, std::vector<int> c,
    std::vector<int> a, std::vector<std::vector<int>> b) {
	vector<int> dp(n+1, INF);
	vector<vector<int>> have(k);
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < a[i]; j++) {
			have[b[i][j]].emplace_back(i);
		}
	}
	dp[0] = 0;
	for (int i = 0; i + m - 1 < n; i++) {
		for (int j : have[c[i]]) {
			bool ok = 1;
			for (int k = 1; k < m; k++) {
				if (!binary_search(all(have[c[i + k]]), (j + k) % m)) {
					ok = 0;
					break;
				}
			}
			if (ok) {
				for (int k = i+1; k <= i+m; k++) {
					ckmin(dp[k], dp[i] + 1);
				}
			}
		}
	}
	return dp[n] == INF ? -1 : dp[n];
}

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