oj.uz

Submission #3970

# Submission time Handle Problem Language Result Execution time Memory
3970 2013-08-31T09:47:57 Z cki86201 Block stacker (kriii1_B) C++
1 / 1
 248 ms 6048 KB 
#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]++;
					D[i-1][j]%=1000000007;
				}
				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[w][h] - w너비, h길이 / sum[w][h] =  D2[w][0] ~ D2[w][h] / 2가 뒤에 붙은 변수는 d[w]로 나눠준 것
		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++){ // 오른쪽 칸이 있는 경우, 1 ~ w-2 길이의 블럭의 합
					D2[i][j] += (sum[k][j-1]*sum2[i-k-1][j]%1000000007); 
					D2[i][j] %= 1000000007;
					D2[i][j] -= (sum[k][j-2]*sum2[i-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]; // 길이가 w-1짜리인 블럭이 있을 때
				D2[i][j]%=1000000007;
				D2[i][j]+=D2[i][j-1]; // 길이가 w짜리인 블럭이 있을 때
				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
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6048 KB Output is correct
2 Correct 0 ms 6048 KB Output is correct
3 Correct 0 ms 6048 KB Output is correct
4 Correct 0 ms 6048 KB Output is correct
5 Correct 0 ms 6048 KB Output is correct
6 Correct 0 ms 6048 KB Output is correct
7 Correct 0 ms 6048 KB Output is correct
8 Correct 4 ms 6048 KB Output is correct
9 Correct 0 ms 6048 KB Output is correct
10 Correct 4 ms 6048 KB Output is correct
11 Correct 36 ms 6048 KB Output is correct
12 Correct 36 ms 6048 KB Output is correct
13 Correct 16 ms 6048 KB Output is correct
14 Correct 36 ms 6048 KB Output is correct
15 Correct 8 ms 6048 KB Output is correct
16 Correct 148 ms 6048 KB Output is correct
17 Correct 204 ms 6048 KB Output is correct
18 Correct 232 ms 6048 KB Output is correct
19 Correct 236 ms 6048 KB Output is correct
20 Correct 248 ms 6048 KB Output is correct