Submission #3982

#	Time	Username	Problem	Language	Result	Execution time	Memory
3982		imsifile	Block stacker (kriii1_B)	C++98	1 / 1	104 ms	3688 KiB

B

#include<stdio.h>
#include<memory.h>
#define mod 1000000007

int k, w, h, col;
long long lng[333][333], tw[333][333], ha[333], dap[333][333];
// 각 color로 길이 j인 막대를 만들 수 있는가

int main(){
	int i, j, t;
	scanf("%d%d%d", &k, &w, &h);
	for(i=0; i<k; i++)lng[i][0]=1;
	for(i=0; i<k; i++){
		scanf("%d", &col), col--;
		for(j=i+1; j<=w; j++)lng[col][j]+=lng[col][j-i-1];
	}
	ha[0]=1;
	for(i=1; i<=w; i++){
		for(j=0; j<k; j++){
			for(t=1; t<=i; t++){
				if(!lng[j][t])continue;
				if(t==i)tw[j][i]++;
				else tw[j][i]+=ha[i-t]-tw[j][i-t];
				if(tw[j][i]>=mod)tw[j][i]-=mod;
				if(tw[j][i]<0)tw[j][i]+=mod;
			}
			ha[i]+=tw[j][i];
			if(ha[i]>=mod)ha[i]-=mod;
		}
	}
	for(j=0; j<=w; j++)dap[0][j]=1;
	for(i=1; i<=h; i++){
		dap[i][0]=1;
		for(j=1; j<=w; j++){
			dap[i][j]=(dap[i][j-1]+dap[i-1][j]*ha[j])%mod;
			for(t=1; t<j; t++){
				dap[i][j]+=(dap[i-1][t]*ha[t])%mod*dap[i][j-t-1];
				dap[i][j]%=mod;
			}
		}
	}
	printf("%lld", dap[h][w]);
	return 0;
}

• Subtask 1: 1 / 1