Submission #44366

#	Time	Username	Problem	Language	Result	Execution time	Memory
44366		Bruteforceman	Tents (JOI18_tents)	C++11	100 / 100	239 ms	36224 KiB

tents

#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
int mem[3003][3003];

long long dp(int H, int W) {
	if(H < 0) return 0;
	if(W < 0) return 0;
	if(H == 0 || W == 0) return 1;
	if(mem[H][W] != -1) return mem[H][W];
	long long ans = 0;
	ans += dp(H - 1, W);
	ans += dp(H - 1, W - 2) * ((W * (W - 1)) / 2); 
	ans += 4LL * dp(H - 1, W - 1) * W;
	ans += dp(H - 2, W - 1) * W * (H - 1);
	ans %= mod;
	return mem[H][W] = ans;
}

int main() {
	memset(mem, -1, sizeof mem);
	int H, W;
	cin >> H >> W;
	long long ans = dp(H, W) - 1;
	if(ans < 0) ans += mod;
	cout << ans << endl;
	return 0;
}

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