Submission #3564

#	Time	Username	Problem	Language	Result	Execution time	Memory
3564		wookayin	Block stacker (kriii1_B)	C++98	1 / 1	160 ms	2164 KiB

B

#include <stdio.h>
 
int K,W,H;
const int mod = 1000000007;
 
int A[303][303];
int B[303];
int Bp[303][303];
int D[303][303];
 
int dat[303];
 
int main()
{
    scanf("%d%d%d",&K,&W,&H);
        for(int i = 0; i < K;i ++){
                scanf("%d",&dat[i]);
                dat[i]--;
        }
        for(int i = 0; i < K; i++){
                A[i][0] = 1;
                for(int k = 0; k < K; k ++){
                        if (dat[k] != i) continue;
                        // length is k + 1, color is i
                        for(int j = 0; j + k + 1 <= W; j++) {
                                A[i][j + k + 1] |= A[i][j];
                        }
                }
        }
        B[0] = 1;
        for(int i = 1; i <= W; i ++) {
                B[i] = 0;
                for(int j = 1; j <= i; j++) {
                        for(int k = 0; k < K; k ++){
                                if (A[k][j]) {
                                        int val = B[i-j] - Bp[i-j][k];
                                        if (val < 0)
                                        {
                                                val += mod;
                                                val %= mod;
                                        }
                                        B[i] = (B[i] + val) % mod;
                                        Bp[i][k] = (Bp[i][k] + val) % mod; 
                                }
                        }
                }
        }
        for(int i = 0; i <= H; i++){
                for(int j = 0; j <= W; j++) {
                        if (i == 0 || j == 0) {
                                D[i][j] = 1;
                                continue;
                        }
                        D[i][j] = (long long)D[i-1][j] * (long long)B[j] % mod;
                        for(int k = 0; k < j; k++) {
                                long long tmp = D[i][j-k-1];
                                tmp *= D[i-1][k];
                                tmp %= mod;
                                tmp *= B[k];
                                tmp %= mod;
                                D[i][j] = (D[i][j] + tmp) % mod;
                        }
                }
        }
        printf("%d\n", D[H][W]);
        return 0;
}

• Subtask 1: 1 / 1