Submission #3883

#	Time	Username	Problem	Language	Result	Execution time	Memory
3883		cki86201	Block stacker (kriii1_B)	C++98	0 / 1	0 ms	6048 KiB

B

#include<stdio.h>

int K,w,h;
long long c[300]={0},cnt=0;
long long block[300][300]={0},bcnt[300]={0};
long long block2[300][300]={0},bcnt2[300]={0};
long long D[300][300]={0},d[300]={0};
long long D2[301][302]={0},sum[301][302]={0};
long long d2[301][302]={0},sum2[301][302]={0};

bool fil[301]={0};
int main()
{
	int i,j,k,t;
	scanf("%d%d%d",&K,&w,&h);
	for(i=0;i<K;i++){ // block 입력
		scanf("%d",&t);
		for(j=0;j<cnt;j++){
			if(c[j]==t){
				block[j][bcnt[j]++]=i+1;
				break;
			}
		}
		if(j==cnt){
			c[cnt]=t;
			block[cnt][0]=i+1,bcnt[cnt]=1;
			cnt++;
		}
	}
	for(i=0;i<cnt;i++){ // 같은 색깔 블럭으로 만들어 질 수 있는 길이
		fil[0]=true;
		for(j=1;j<=w;j++) fil[j]=false;
		for(j=1;j<=w;j++)
		{
			for(k=0;k<bcnt[i];k++){
				if(j<block[i][k]) break;
				if(fil[j-block[i][k]]){
					fil[j]=true;
					block2[i][bcnt2[i]++]=j;
					break;
				}
			}
		}
	}
	for(i=1;i<=w;i++){ // D[i][j] - i길이에서 j색으로 끝나는 가지수 , d[i] - i길이의 가지수
		for(j=0;j<cnt;j++){
			for(k=0;k<bcnt2[j];k++){
				if(i<block2[j][k]) break;
				else if(i==block2[j][k]) D[i-1][j]++;
				else{
					D[i-1][j]+=d[i-block2[j][k]-1]-D[i-block2[j][k]-1][j];
					if(D[i-1][j]<0) D[i-1][j]+=1000000007;
					D[i-1][j]%=1000000007;
				}
			}
			d[i-1]+=D[i-1][j];
			d[i-1]%=1000000007;
		}
	}
	for(i=1;i<=w;i++){
		D2[i][0]=1,d2[i][0]=0,sum[i][0]=0;
		D2[i][1]=sum[i][1]=d[i-1];
		d2[i][1]=sum2[i][1]=1;
		for(j=2;j<=h+1;j++){
			if(i==1)
				D2[i][j]=d2[i][j-1];
			else{
				D2[i][j]=d2[i-1][j];
				for(k=1;k<=i-2;k++){
					D2[i][j] += (sum[k][j-1]*sum2[w-k-1][j])%1000000007;
					D2[i][j] %= 1000000007;
					D2[i][j] -= (sum[k][j-2]*sum2[w-k-1][j-1])%1000000007;
					if(D2[i][j]<0) D2[i][j]+=1000000007;
					D2[i][j] %= 1000000007;
				}
				D2[i][j]+=D2[i-1][j-1];
				D2[i][j]%=1000000007;
				D2[i][j]+=D2[i][j-1];
				D2[i][j]%=1000000007;
			}
			d2[i][j]=D2[i][j];
			D2[i][j]=(D2[i][j] * d[i-1]) % 1000000007;
			sum[i][j]=sum[i][j-1]+D2[i][j];
			sum[i][j]%=1000000007;
			sum2[i][j]=sum2[i][j-1]+d2[i][j];
			sum2[i][j]%=1000000007;
		}
	}
	printf("%lld",sum2[w][h+1]);
	return 0;
}

• Subtask 1: 0 / 1