Submission #448499

#	Time	Username	Problem	Language	Result	Execution time	Memory
448499		nonsensenonsense1	Painting Walls (APIO20_paint)	C++17	100 / 100	1233 ms	14264 KiB

paint

#include "paint.h"

const int N = 100000;
const int M = 50000;
int u[M], d[M];
std::vector<int> like[N];

int minimumInstructions(int n, int m, int k, std::vector<int> c, std::vector<int> a, std::vector<std::vector<int> > b) 
{
	for (int i = 0; i < m; ++i) for (int j = 0; j < a[i]; ++j) like[b[i][j]].push_back(i);
	int pre = -1, last = -1, amt = 1;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < (int)like[c[i]].size(); ++j) {
			int cur = i - like[c[i]][j];
			cur = (cur % m + m) % m;
			if (u[cur] != i) d[cur] = 0;
			++d[cur];
			u[cur] = i + 1;
			if (d[cur] >= m) {
				if (i - m > last) return -1;
				if (i - m <= pre) last = i;
				else {
					pre = last;
					last = i;
					++amt;
				}
			}
		}
	}
	if (last < n - 1) return -1;
	return amt;
}

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