Submission #374904

#	Time	Username	Problem	Language	Result	Execution time	Memory
374904		MilosMilutinovic	Paint By Numbers (IOI16_paint)	C++14	100 / 100	465 ms	43372 KiB

paint

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

const int mxN=2e5+5, mxK=100;
int n, k, sum[mxN+1], dp3[mxN], dp4[mxN];
bool dp1[mxN][mxK+1], dp2[mxN][mxK+1];

string solve_puzzle(string s, vector<int> a) {
	int n=(int)s.length(), k=(int)a.size();	
	for(int i=0; i<n; ++i)
		sum[i+1]=sum[i]+(s[i]=='_');
	dp1[0][0]=dp2[n][k]=1;
	for(int i=0; i<n; ++i) {
		for(int j=0; j<=k; ++j) {
			if(s[i]^'X')
				dp1[i+1][j]|=dp1[i][j];
			if(j<k&&i+a[j]<n&&s[i+a[j]]^'X'&&sum[i]==sum[i+a[j]])
				dp1[i+a[j]+1][j+1]|=dp1[i][j];
		}
	}
	for(int i=n; i; --i) {
		for(int j=0; j<=k; ++j) {
			if(s[i-1]^'X')
				dp2[i-1][j]|=dp2[i][j];
			if(j&&i-a[j-1]>0&&s[i-a[j-1]-1]^'X'&&sum[i]==sum[i-a[j-1]])
				dp2[i-a[j-1]-1][j-1]|=dp2[i][j];
		}
	}
	for(int i=0; i<n; ++i) {
		for(int j=0; j<=k; ++j)
			dp3[i]|=dp1[i+1][j]&&dp2[i][j];
		for(int j=0; j<k; ++j) {
			if(i+a[j]<=n&&dp1[i][j]&&dp2[i+a[j]][j+1]&&sum[i+a[j]]==sum[i]) {
				++dp4[i];
				--dp4[i+a[j]];
			}
		}
		dp4[i+1]+=dp4[i];
		s[i]=(dp3[i]&&dp4[i]?'?':dp3[i]?'_':'X');
	}
	return s;
}

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