제출 #132436

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
132436		wilwxk	Paint By Numbers (IOI16_paint)	C++14	80 / 100	94 ms	400 KiB

paint

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

const int MAXN=105;
string v, respf;
vector<int> qv;
short dp[MAXN][105];
int soma[2][MAXN];
int n, q;

int psum(int ini, int fim, int k) {
	if(fim>=n) return MAXN;
	return soma[k][fim]- (ini==0 ? 0 : soma[k][ini-1]);
}

short fazdp(int ind, int k) {
	if(ind>=n) return k>=q;
	if(v[ind]=='X'&&k>=q) return 0;
	if(dp[ind][k]!=-1) return dp[ind][k];
	// printf("call %d %d\n",ind, k);

	dp[ind][k]=0;
	int fim=ind+qv[k]-1;
	int val=psum(ind, fim, 0);
	int val2=psum(ind, fim, 1);
	
	if(val==0&&v[fim+1]!='X') dp[ind][k]|=fazdp(fim+2, k+1);
	if(v[ind]!='X') dp[ind][k]|=fazdp(ind+1, k);
	
	// printf("dp %d %d >> %d // %d %d\n", ind, k, dp[ind][k], val, val2);
	return dp[ind][k];
}
void recalc() {
	soma[0][0]=soma[1][0]=0;
	for(int i=0; i<n; i++) {
		if(i!=0) soma[0][i]=soma[0][i-1], soma[1][i]=soma[1][i-1];
		soma[0][i]+=(v[i]=='_');
		soma[1][i]+=(v[i]=='X');
	}
	memset(dp, -1, sizeof(dp));
	fazdp(0, 0);
}




bool testa(int ind, char tipo) {
	v[ind]=tipo;
	recalc();
	v[ind]='.';
	return dp[0][0];
}

string solve_puzzle(string s, vector<int> c) {
    n=s.size(); v=s; v.push_back('_');
    respf=s;
    qv=c; q=qv.size();

    for(int i=0; i<n; i++) {
    	if(s[i]!='.') continue;

    	bool a=testa(i, '_');
    	bool b=testa(i, 'X');

    	// printf("%d >> ab %d %d\n\n", i, a, b);

    	if(a&&b) respf[i]='?';
    	else if(a) respf[i]='_';
    	else respf[i]='X';
    }

    return respf;
}

컴파일 시 표준 에러 (stderr) 메시지

paint.cpp: In function 'short int fazdp(int, int)':
paint.cpp:26:6: warning: unused variable 'val2' [-Wunused-variable]
  int val2=psum(ind, fim, 1);
      ^~~~

• 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