제출 #836638

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
836638		NK_	Tents (JOI18_tents)	C++17	100 / 100	97 ms	70824 KiB

tents

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
 
using namespace std;
 
#define nl '\n'
#define pb push_back
#define pf push_front
 
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;
 
using ll = long long;
using pl = pair<ll, ll>;
using vpl = V<pl>;
using vl = V<ll>;
 
using db = long double;
 
template<class T> using pq = priority_queue<T, V<T>, less<T>>;
 
const int MOD = 1e9 + 7;
const ll INFL = ll(1e17);
const int LG = 19;

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int H, W; cin >> H >> W; 

	V<vl> dp(H+1, vl(W+1, 0));
	for(int r = 0; r <= H; r++) for(int c = 0; c <= W; c++) {
		if (r == 0 || c == 0) dp[r][c] = 1;
		else {
			dp[r][c] = (dp[r-1][c] + dp[r-1][c-1] * 4LL * c) % MOD;

			if (r >= 2) {
				dp[r][c] += (dp[r-2][c-1] * (r - 1) * 1LL * c) % MOD;
				dp[r][c] %= MOD;
			}

			if (c >= 2) {
				dp[r][c] += (dp[r-1][c-2] * (c * 1LL * (c - 1)) / 2) % MOD;
				dp[r][c] %= MOD;
			}
		}
	}
	
	dp[H][W] -= 1;
	cout << (dp[H][W] + MOD) % MOD << nl;

	exit(0-0);
} 	

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