Submission #506246

#	Time	Username	Problem	Language	Result	Execution time	Memory
506246		sliviu	Paint By Numbers (IOI16_paint)	C++14	0 / 100	0 ms	204 KiB

paint

#include <bits/stdc++.h>
#include "paint.h"

using namespace std;

string solve_puzzle(string s, vector<int> c) {
	string ans = "";
	int n = s.length(), k = c.size();
	s = '$' + s;
	vector<int> canw(n + 2), canb(n + 2), cnt(n + 1);
	vector<vector<int>> dpb(n + 2, vector<int>(k + 2)), dpa(n + 2, vector<int>(k + 2));
	for (int i = 1; i <= n + 1; ++i)
		cnt[i] = cnt[i - 1] + (s[i] == '_');
	dpb[0][0] = dpa[n + 1][k] = 1;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j <= k; ++j) {
			if (s[i + 1] != 'X')
				dpb[i + 1][j] |= dpb[i][j];
			if (j < k&& i + c[j] + 1 <= n && s[i + c[j] + 1] != 'X' && cnt[i] == cnt[i + c[j]])
				dpb[i + c[j] + 1][j + 1] |= dpb[i][j];
		}

	for (int i = n + 1; i > 1; --i)
		for (int j = 0; j <= k; ++j) {
			if (s[i - 1] != 'X')
				dpa[i - 1][j] |= dpa[i][j];
			if (j && i - c[j - 1] - 1 >= 1 && s[i - c[j - 1] - 1] != 'X' && cnt[i] == cnt[i - c[j - 1]])
				dpa[i - c[j - 1] - 1][j - 1] |= dpa[i][j];
		}

	for (int i = 0; i <= n; ++i)
		for (int j = 0; j <= k; ++j) {
			if (s[i] != 'X' && dpb[i][j] && dpa[i][j])
				canw[i] |= 1;
			if (j < k && i + c[j] <= n && dpb[i][j] && dpa[i + c[j] + 1][j + 1] && cnt[i] == cnt[i + c[j]])
				++canb[i + 1], --canb[i + c[j] + 1];
		}
  	return ans;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 3
• Subtask 3: 0 / 22
• Subtask 4: 0 / 27
• Subtask 5: 0 / 21
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10