Submission #1224908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224908		PenguinsAreCute	Tents (JOI18_tents)	C++17	48 / 100	271 ms	589824 KiB

tents

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int main() {
	int h, w;
	cin >> h >> w;
	int dp[h+1][w+1][w+1];
	memset(dp,0,sizeof(dp));
	dp[0][w][0] = 1;
	for(int i=0;i<h;i++) {
		memcpy(dp[i+1],dp[i],sizeof(dp[i]));
		for(int j=0;j<=w;j++)
			for(int k=1;k<=w;k++)
				dp[i+1][j][k-1] = (dp[i+1][j][k-1] + 1LL * k * dp[i][j][k]) % MOD;
		for(int j=1;j<=w;j++)
			for(int k=0;k<w;k++)
				dp[i+1][j-1][k+1] = (dp[i+1][j-1][k+1] + 1LL * j * dp[i][j][k]) % MOD;
		for(int j=2;j<=w;j++)
			for(int k=0;k<=w;k++)
				dp[i+1][j-2][k] = (dp[i+1][j-2][k] + 1LL * j * (j - 1) / 2 % MOD * dp[i][j][k]) % MOD;
	}
	int ans = MOD - 1;
	for(int j=0;j<=w;j++)
		for(int k=0,p4=1;k<=w;k++,p4=(4LL*p4)%MOD)
			ans = (ans + 1LL * dp[h][j][k] * p4) % MOD;
	cout << ans;
}

• Subtask 1: 48 / 48
• Subtask 2: 0 / 52