Submission #927263

#	Time	Username	Problem	Language	Result	Execution time	Memory
927263		TAhmed33	Painting Walls (APIO20_paint)	C++17	51 / 100	1537 ms	50896 KiB

paint

#include <bits/stdc++.h>
using namespace std;
int minimumInstructions (int n, int m, int k, vector <int> c, vector <int> a, vector <vector <int>> b) {
	vector <int> occ[k];
	for (int i = 0; i < m; i++) {
		for (auto j : b[i]) {
			occ[j].push_back(i);
		}
	}
	vector <bool> ok(n, 0);
	vector <vector <int>> dp(n);
	for (int i = n - 1; i >= 0; i--) {
		dp[i].resize(occ[c[i]].size());
		bool flag = 0;
		for (int j = 0; j < (int)dp[i].size(); j++) {
			dp[i][j] = 1;
			int l = (occ[c[i]][j] + 1) % m;
			if (i + 1 < n) {
				auto z = lower_bound(occ[c[i + 1]].begin(), occ[c[i + 1]].end(), l) - occ[c[i + 1]].begin();
				if (z != occ[c[i + 1]].size() && occ[c[i + 1]][z] == l) {
					dp[i][j] += dp[i + 1][z];
				}
			}
			flag |= dp[i][j] >= m;
		}
		ok[i] = flag;
	}
	vector <int> dp2(n);
	for (int i = n - 1; i >= 0; i--) {
		dp2[i] = n + 1;
		if (ok[i]) {
			if (n - i <= m) {
				dp2[i] = 1;
			} else {
				int mn = n + 1;
				for (int j = i + 1; j <= i + m; j++) {
					mn = min(mn, dp2[j]);
				}
				dp2[i] = 1 + mn;
			}
		}
	}
	return dp2[0] <= n ? dp2[0] : -1;
}
/*
int main () {
	cout << minimumInstructions(8, 3, 5, {3, 3, 1, 3, 4, 4, 2, 2}, {3, 2, 2}, {{0, 1, 2}, {2, 3}, {3, 4}});	
	cout << minimumInstructions(5, 4, 4, {1, 0, 1, 2, 2}, {2, 1, 1, 1}, {{0, 1}, {1}, {2}, {3}});
}*/

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:20:11: warning: comparison of integer expressions of different signedness: 'long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     if (z != occ[c[i + 1]].size() && occ[c[i + 1]][z] == l) {
      |         ~~^~~~~~~~~~~~~~~~~~~~~~~

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