Submission #21294

#	Time	Username	Problem	Language	Result	Execution time	Memory
21294		gs14004	Block stacker (kriii1_B)	C++11	1 / 1	76 ms	3840 KiB

B

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;

int n, w, h, ok[305][305];
lint d1[305][305], sum[305];
lint dp[305][305];

int main(){
	cin >> n >> w >> h;
	for(int i=1; i<=n; i++) ok[i][0] = 1;
	for(int i=1; i<=n; i++){
		int x;
		cin >> x;
		for(int j=0; j+i<=w; j++){
			ok[x][j+i] |= ok[x][j];
		}
	}
	d1[0][0] = 1;
	sum[0] = 1;
	for(int i=1; i<=w; i++){
		for(int j=1; j<=n; j++){
			for(int k=0; k<i; k++){
				if(ok[j][i-k]){
					d1[i][j] += sum[k] - d1[k][j] + mod;
				}
			}
			d1[i][j] %= mod;
			sum[i] += d1[i][j];
		}
		sum[i] %= mod;
	}
	for(int i=0; i<=w; i++) dp[0][i] = 1;
	for(int i=1; i<=h; i++){
		dp[i][0] = 1;
		for(int j=1; j<=w; j++){
			dp[i][j] = dp[i-1][j] * sum[j] % mod;
			dp[i][j] += dp[i][j-1];
			for(int k=1; k<j; k++){
				dp[i][j] += (dp[i-1][k] * sum[k] % mod) * dp[i][j-k-1] % mod;
			}
			dp[i][j] %= mod;
		}
	}
	cout << dp[h][w];
}

• Subtask 1: 1 / 1