Submission #1201570

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201570		A_M_Namdar	Painting Walls (APIO20_paint)	C++20	0 / 100	1 ms	2632 KiB

paint

#include "paint.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int dp[2][N];
vector<int> pos[N];
bool mark[N];
/*
void input() {
	cin >> n >> m >> k;
	for (int i = 0; i < n; i++) 
		cin >> c[i];
	for (int i = 0; i < m; i++) {
		cin >> a[i];
		for (int j = 0; j < a[i]; j++) {
			int x;
			cin >> x;
			b[i].push_back(x);
			pos[x].push_back(i);
		}
	}
}*/

int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> a, vector<vector<int>> b) {
	for (int i = 0; i < n; i++) 
		for (int j: b[i]) 
			pos[j].push_back(i);
	vector<int> vec;
	for (int i = 0; i < m; i++) 
		vec.push_back(i);
	for (int i = n - 1; i >= 0; i--) {
		vector<int> vec2;
		for (int j: pos[c[i]]) {
			vec2.push_back(j);
			dp[i & 1][j] = dp[(i + 1) & 1][(j + 1) % m] + 1;
			if (dp[i & 1][j] >= m) 
				mark[i] = true;
		}
		for (int j: vec) 
			dp[(i + 1) & 1][j] = 0;
		swap(vec, vec2);
//		cout << i << ' ' << mark[i] << '\n';
	}
	if (!mark[0]) 
		return -1;
	int p = m, ans = 1;
	while (p < n) {
		for (int i = 0; i < m; i++) {
			if (p - i >= 0 && mark[p - i]) {
				ans++;
				p = p - i + m;
				break;
			}
			if (i == m - 1) 
				return -1;
		}
	}
	return ans;
}
/*
int main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	input();
	solve();
}*/

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