Submission #1021799

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021799		vjudge1	Paint By Numbers (IOI16_paint)	C++17	80 / 100	2067 ms	20500 KiB

paint

#include <bits/stdc++.h>
using namespace std;

const int maxn = 5e3 + 100;

int n, k;
bool dp[maxn][maxn];
int a[maxn];
int b[maxn];
int c[maxn];
string s;

bool ok(int l, int r, int c){
	if(c){
		if(b[r] > b[l-1]) return 0;
		return 1;
	} else{
		if(a[r] > a[l-1]) return 0;
		return 1;
	}
}

bool ok(){
	for(int i = 1; i <= n; i++){
		a[i] = a[i-1]; b[i] = b[i-1];
		if(s[i] == 'X') a[i]++;
		if(s[i] == '_') b[i]++;
		fill(dp[i], dp[i] + k + 1, 0);
	}
	dp[0][0] = 1;
	for(int i = 1; i <= n; i++){
		for(int j = 0; j <= k; j++){
			if(ok(i, i, 0) && dp[i-1][j]){
				dp[i][j] = 1;
			}
			if(j){
				int l = i - c[j] - 1;
				if(j == 1) l++;
				if(l >= 0 && dp[l][j-1] && ok(i - c[j] + 1, i, 1) && (j == 1 || ok(l+1, l+1, 0))){
					dp[i][j] = 1;
				}
			}
		}
	}
	return dp[n][k];
}

string solve_puzzle(std::string S, std::vector<int> C){
	s = S;
	n = s.size();
	s = "#" + s; k = C.size();
	for(int i = 1; i <= k; i++){
		c[i] = C[i-1];
	}
	string res;
	vector<int> ans = {'.', '_', 'X', '?'};
	for(int i = 1; i <= n; i++){
		int x = 0;
		if(s[i] == '.'){
			s[i] = 'X';
			if(ok()) x |= 2;
			s[i] = '_';
			if(ok()) x |= 1;
			s[i] = '.';
		} else if(s[i] == 'X') x = 2;
		else x = 1;
		res.push_back(ans[x]);
	}
	return res;
}

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