Submission #131094

#	Time	Username	Problem	Language	Result	Execution time	Memory
131094		maruii	Tents (JOI18_tents)	C++14	100 / 100	157 ms	21644 KiB

tents

#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
int A[3001][3001];

int f(int n, int m) {
	if (n < 0 || m < 0) return 0;
	if (!n || !m) return 1;
	if (n > m) swap(n, m);
	if (A[n][m]) return A[n][m];
	return A[n][m] = (f(n, m - 1) + n * (n - 1) / 2ll * f(n - 2, m - 1) + 4ll * n * f(n - 1, m - 1) + 1ll * n * (m - 1) * f(n - 1, m - 2)) % mod;
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int H, W; cin >> H >> W;
	cout << f(H, W) - 1;
	return 0;
}

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