제출 #236885

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
236885		islingr	Tents (JOI18_tents)	C++14	100 / 100	195 ms	72544 KiB

tents

#include <iostream>
using namespace std;

#define rep(i, a, b) for (ll i = (a); i <= (b); ++i)

using ll = long long;

const int N = 3 << 10, M = 1e9 + 7;
ll dp[N][N];

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int h, w; cin >> h >> w;
	rep(i, 0, h) dp[i][0] = 1;
	rep(j, 0, w) dp[0][j] = 1;
	rep(i, 1, h) {
		rep(j, 1, w) {
			auto add = [&](ll x) {
				dp[i][j] += x;
				if (M <= dp[i][j]) dp[i][j] -= M;
			};
			if (i != 1) add(i * (i - 1) / 2 % M * dp[i - 2][j - 1] % M);
			add(4 * i * dp[i - 1][j - 1] % M);
			add(dp[i][j - 1]);
			if (j != 1) add(i * (j - 1) % M * dp[i - 1][j - 2] % M);
		}
	}
	cout << (dp[h][w] + M - 1) % M;
}

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