Submission #387131

#	Time	Username	Problem	Language	Result	Execution time	Memory
387131		milleniumEeee	Painting Walls (APIO20_paint)	C++17	0 / 100	1562 ms	8940 KiB

paint

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

const int MAXN = (int)1e5 + 5;
const int INF = 1e9 + 7;

int pos[MAXN];
int dp[MAXN];
int pref[MAXN];

int minimumInstructions(int N, int M, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
	memset(pos, -1, sizeof(pos));
	for (int i = 0; i < M; i++) {
		for (int el : B[i]) {
			pos[el] = i;
		}
	}
	for (int i = 0; i < N; i++) {
		if (pos[C[i]] == -1) {
			return -1;
		}
	}
	auto nxt = [&](int p) {
		if (p + 1 < M) {
			return p + 1;
		} else {
			return 0;
		}
	};
	for (int i = 0; i + 1 < N; i++) {
		int before = (i > 0 ? pref[i - 1] : 0);
		pref[i] = before + (pos[C[i + 1]] == nxt(pos[C[i]]));
	}
		
	auto get = [&](int l, int r) {
		return pref[r - 1] - pref[l - 1];
	};
	auto can = [&](int l, int r) {
		if (r - l + 1 == M && get(l, r) == M - 1) {
			return true;
		} else {
			return false;
		}
	};
	fill(dp, dp + MAXN, INF);
	if (can(0, M - 1)) {
		for (int i = 0; i < M; i++) {
			dp[i] = 1;
		}
	}
	for (int i = M; i < N; i++) {
		if (can(i - M + 1, i)) {
			int best = INF;
			for (int j = i - M; j < i; j++) {
				if (j >= 0) {
					best = min(best, dp[j]);					
				}
			}
			dp[i] = best + 1;
			for (int j = i - M + 1; j <= i; j++) {
				dp[j] = min(dp[j], dp[i]);
			}
		}
	}
	if (dp[N - 1] < INF) {
		return dp[N - 1];
	} else {
		return -1;
	}
}

/*
5 3 10
0 2 1 4 3
2 0 4
2 3 2
1 1
*/

Compilation message (stderr)

paint.cpp: In function 'int minimumInstructions(int, int, int, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
paint.cpp:38:34: warning: array subscript -1 is below array bounds of 'int [100005]' [-Warray-bounds]
   38 |   return pref[r - 1] - pref[l - 1];
      |                        ~~~~~~~~~~^

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