Submission #1175723

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175723		stdfloat	Painting Walls (APIO20_paint)	C++20	0 / 100	0 ms	328 KiB

paint

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

#define all(v)    (v).begin(), (v).end()

int minimumInstructions(int n, int m, int K, vector<int> C, vector<int> A, vector<vector<int>> B) {
	map<int, int> mp;
	for (auto i : C)
		mp[i] = 1;
	for (auto i : B) {
		for (auto j : i)
			mp[j] = 1;
	}

	K = 0;
	for (auto &i : mp)
		i.second = K++;

	for (auto &i : C)
		i = mp[i];
	for (auto &i : B) {
		for (auto &j : i)
			j = mp[j];
	}

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

	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];
		}
	}

	// cout << "F\n";
	// for (auto i : F) {
	// 	for (auto j : i)
	// 		cout << j << ' ';
	// 	cout << endl;
	// }
	// cout << "\nC\n";
	// for (auto i : C)
	// 	cout << i << ' ';
	// cout << "\ndp1\n";
	// for (auto i : dp1) {
	// 	for (auto j : i)
	// 		cout << j << ' ';
	// 	cout << endl;
	// }
	// cout << "\ndp2\n";
	// for (auto i : dp2) {
	// 	for (auto j : i)
	// 		cout << j << ' ';
	// 	cout << endl;
	// }
	// cout << endl;

	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));

		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: 0 / 15
• Subtask 3: 0 / 13
• Subtask 4: 0 / 23
• Subtask 5: 0 / 37