Submission #965769

#	Time	Username	Problem	Language	Result	Execution time	Memory
965769		Gromp15	Painting Walls (APIO20_paint)	C++17	100 / 100	948 ms	270004 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<vector<int>> who(k), where(m);
	for (int i = 0; i < m; i++) for (int x : b[i]) who[x].emplace_back(i);
	for (int i = 0; i < n; i++) {
		for (int x : who[c[i]]) {
			where[((x - i) % m + m) % m].emplace_back(i);
		}
	}
	for (int i = 0; i < m; i++) {
		where[i].erase(unique(all(where[i])), where[i].end());
	}
	vector<bool> ok(n);
	for (int i = 0; i < m; i++) {
		int lst = -2, got = 0;
		for (int j : where[i]) {
			if (j - lst > 1) {
				got = 1, lst = j;
			}
			else got++, lst = j;
			if (got >= m) {
				ok[j - m + 1] = 1;
			}
		}
	}
	vector<int> dp(n + 1, INF);
	dp[0] = 0;
	multiset<int> good;
	vector<vector<int>> add(n+1), rem(n+1);
	for (int i = 0; i <= n; i++) {
		for (int x : add[i]) good.insert(x);
		for (int x : rem[i]) good.erase(good.find(x));
		if (good.size()) ckmin(dp[i], *good.begin());
		if (i < n && ok[i]) {
			add[i+1].emplace_back(dp[i] + 1);
			if (i + m + 1 <= n) rem[i+m+1].emplace_back(dp[i] + 1);
		}
	}
	return dp[n] == INF ? -1 : dp[n];
}

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