Submission #570971

#	Time	Username	Problem	Language	Result	Execution time	Memory
570971		grt	Painting Walls (APIO20_paint)	C++17	100 / 100	373 ms	14640 KiB

paint

//GRT_2018
#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

int minimumInstructions(int n, int m, int k, vi c, vi len, vector<vi>acceptable) {
	vector<vi>who(k);
	for(int i = 0; i < m; ++i) {
		for(int ac : acceptable[i]) {
			who[ac].PB(i);
		}
	}
	vi dp((int)who[c[0]].size());
	for(int &x : dp) x = 1;
	vi state(n);
	for(int &x : state) x = 0;
	if(m == 1) state[0] = 1;
	for(int i = 1; i < n; ++i) {
		int ptr = 0;
		vi new_dp((int)who[c[i]].size());
		for(int &x : new_dp) x = 1;
		int id = 0;
		for(int j : who[c[i]]) {
			while(ptr < (int)who[c[i - 1]].size() && who[c[i - 1]][ptr] < j - 1) {
				ptr++;
			}
			if(ptr < (int)who[c[i - 1]].size() && who[c[i - 1]][ptr] == j - 1) {
				new_dp[id] = dp[ptr] + 1;
			}
			if(j == 0 && (int)who[c[i - 1]].size() != 0 && who[c[i - 1]].back() == m - 1) {
				new_dp[id] = dp.back() + 1;
			}
			id++;
		}
		int mx = -1;
		for(int x : new_dp) mx = max(mx, x);
		if(mx >= m) {
			state[i] = 1;
		}
		dp.swap(new_dp);
	}
	vi S = {};
	for(int i = 0; i < n; ++i) {
		if(!state[i]) continue;
		while((int)S.size() > 1 && S[(int)S.size() - 2] + m >= i) S.pop_back();
		S.PB(i);
	}
	for(int i = 1; i < (int)S.size(); ++i) {
		if(S[i - 1] + m < S[i]) {
			return -1;
		}
	}
	if(S.empty() || S.back() != n - 1) return -1;
	return (int)S.size();
}

//int main() {
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	//cout << minimumInstructions(8, 3, 5, {3, 3, 1, 3, 4, 4, 2, 2}, {3, 2, 2}, {{0, 1, 2}, {2, 3}, {3, 4}}) << "\n";
	//cout << minimumInstructions(5, 4, 4, {1, 0, 1, 2, 2}, {2, 1, 1, 1}, {{0, 1}, {1}, {2}, {3}}) << "\n";
//}

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