Submission #1175734

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175734		stdfloat	Painting Walls (APIO20_paint)	C++20	51 / 100	253 ms	589824 KiB

paint

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

int minimumInstructions(int n, int m, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
	vector<vector<int>> F(K);
	for (int i = 0; i < m; i++) {
		for (auto j : B[i])
			F[j].push_back(i);
	}
	B.clear();

	vector<vector<bool>> dp1(n, vector<bool>(m)), dp2(n, vector<bool>(m)); //dp1: 0 ... x,  dp2: x ... m - 1
	for (int i = 0; i < n; i++) {
		dp1[i][0] = (!F[C[i]].empty() && !F[C[i]][0]);

		if (i) {
			for (auto j : F[C[i]])
				if (j) dp1[i][j] = dp1[i - 1][j - 1];
		}
	}
	for (int i = n - 1; i >= 0; i--) {
		dp2[i][m - 1] = (!F[C[i]].empty() && F[C[i]].back() == m - 1);

		if (i != n - 1) {
			for (auto j : F[C[i]])
				if (j < m - 1) dp2[i][j] = dp2[i + 1][j + 1];
		}
	}

	vector<int> dp(n, (int)1e9);
	for (int i = m - 1; i < n; i++) {
		int mn = (int)1e9;
		for (int j = i - m; j < i; j++)
			mn = min(mn, (~j ? dp[j] : 0));

		if (mn == (int)1e9) continue;

		bool tr = dp1[i][m - 1];
		for (int j = 1; j < m && !tr; j++)
			tr = (dp2[i - m + 1][j] && dp1[i][j - 1]);

		if (tr) dp[i] = mn + 1;
	}

	return (dp[n - 1] == (int)1e9 ? -1 : dp[n - 1]);
}

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