제출 #3108

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
3108		ainta	Block stacker (kriii1_B)	C++98	1 / 1	688 ms	2596 KiB

B

#include<stdio.h>
int K,W,H,i,j,k,C[301];
bool V[301][301];
long long a,b,Mod=1000000007,t,Res,D[302][301],D2[301][301],S[301];
int main()
{
	scanf("%d%d%d",&K,&W,&H);
	for(i=1;i<=K;i++){
		scanf("%d",&C[i]);
		V[C[i]][i]=true;
	}
	for(i=1;i<=K;i++){
		for(j=1;j<=W-i;j++){
			V[C[i]][j+i]|=V[C[i]][j];
		}
	}
	S[0]=1;
	for(i=1;i<=W;i++){
		for(j=1;j<=i;j++){
			for(k=1;k<=K;k++){
				if(!V[k][j])continue;
				D2[i][k]=D2[i][k]+S[i-j]-D2[i-j][k];
				if(D2[i][k]>=Mod)D2[i][k]-=Mod;
				if(D2[i][k]<0)D2[i][k]+=Mod;
			}
		}
		for(j=1;j<=k;j++)S[i]+=D2[i][j];
		S[i]%=Mod;
	}
	D[1][0]=1;
	for(i=1;i<=W;i++){
		D[1][i]=D[1][i-1];
		for(j=1;j<i;j++){
			D[1][i]+=D[1][i-j-1]*S[j];
			D[1][i]%=Mod;
		}
		D[1][i]+=S[i];
		D[1][i]%=Mod;
	}
	for(i=2;i<=H;i++){
		D[i][0]=1;
		for(j=1;j<=W;j++){
			D[i][j]=D[i][j-1];
			D[i][j]=(D[i][j]+D[i-1][j]*S[j])%Mod;
			for(k=1;k<j;k++){
				a=S[k]*D[i][j-k-1]%Mod;
				a=a*D[i-1][k]%Mod;
				D[i][j]+=a;
				D[i][j]%=Mod;
			}
		}
	}
	printf("%lld\n",D[H][W]);
}

• Subtask 1: 1 / 1