Submission #1298229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1298229		Jawad_Akbar_JJ	Painting Walls (APIO20_paint)	C++20	100 / 100	130 ms	13656 KiB

paint

#include <iostream>
#include <vector>
#include <deque>

using namespace std;
const int N = 1<<17;
int seen[N], dp[N], Mx[N];
vector<int> ind[N];

int minimumInstructions(int n, int m, int k, vector<int> c, vector<int> A, vector<vector<int>> B){
	for (int i=0;i<m+m;i++){
		for (int j : B[i % m])
			ind[j].push_back(i);
	}

	deque<int> v = {n};
	for (int j=n-1;j>=0;j--){
		if (v.size() > 0 and v.front() - j > m)
			v.pop_front();

		int mx = 0;
		for (int id : ind[c[j]]){
			Mx[id] = 1;
			if (seen[id+1] == j + 1)
				Mx[id] = Mx[id+1] + 1;
			mx = max(mx, Mx[id]);
			seen[id] = j;
		}
		dp[j] = (mx >= m) ? dp[v.front()] + 1 : n + 1;
		while (v.size() and dp[v.back()] >= dp[j])
			v.pop_back();
		v.push_back(j);
	}
	return (dp[0] >= n + 1 ? -1 : dp[0]);
}

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