Submission #3982

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
3982	2013-08-31T09:50:36 Z	imsifile	Block stacker (kriii1_B)	C++	1 / 1	104 ms	3688 KB

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.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	3688 KB	Output is correct
2	Correct	0 ms	3688 KB	Output is correct
3	Correct	0 ms	3688 KB	Output is correct
4	Correct	0 ms	3688 KB	Output is correct
5	Correct	0 ms	3688 KB	Output is correct
6	Correct	0 ms	3688 KB	Output is correct
7	Correct	0 ms	3688 KB	Output is correct
8	Correct	4 ms	3688 KB	Output is correct
9	Correct	4 ms	3688 KB	Output is correct
10	Correct	0 ms	3688 KB	Output is correct
11	Correct	16 ms	3688 KB	Output is correct
12	Correct	16 ms	3688 KB	Output is correct
13	Correct	8 ms	3688 KB	Output is correct
14	Correct	20 ms	3688 KB	Output is correct
15	Correct	4 ms	3688 KB	Output is correct
16	Correct	64 ms	3688 KB	Output is correct
17	Correct	80 ms	3688 KB	Output is correct
18	Correct	104 ms	3688 KB	Output is correct
19	Correct	84 ms	3688 KB	Output is correct
20	Correct	96 ms	3688 KB	Output is correct