Submission #1223403

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223403		siewjh	Tents (JOI18_tents)	C++20	100 / 100	161 ms	71348 KiB

tents

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 3005;
const ll mod = 1e9 + 7;
ll memo[MAXN][MAXN];
ll dp(ll r, ll c){
	if (r <= 0 || c <= 0) return 1;
	if (memo[r][c] != -1) return memo[r][c];
	ll ans = dp(r - 1, c);
	ans = (ans + 4 * c * dp(r - 1, c - 1)) % mod;
	if (r >= 2) ans = (ans + c * (r - 1) * dp(r - 2, c - 1)) % mod;
	if (c >= 2) ans = (ans + c * (c - 1) / 2 * dp(r - 1, c - 2)) % mod;
	return memo[r][c] = ans;
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll h, w; cin >> h >> w;
	memset(memo, -1, sizeof(memo));
	cout << (dp(h, w) + mod - 1) % mod;
}

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