제출 #305618

#제출 시각아이디문제언어결과실행 시간메모리
305618youngyojunTents (JOI18_tents)C++17
100 / 100
305 ms106232 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int MOD = 1000000007;
const int MAXH = 3005;
const int MAXW = 3005;
 
int dp[MAXW][MAXH], ds[MAXW][MAXH], dks[MAXW][MAXH];
 
int H, W;
 
int main() {
	for(int i = 0; i < MAXH; i++) dp[0][i] = dp[i][0] = 1;
	for(int i = 0; i < MAXH; i++) ds[0][i] = i+1;
	dks[0][0] = 1; for(int i = 1; i < MAXH; i++) dks[0][i] = (dks[0][i-1] + i+1) % MOD;
 
	cin >> H >> W;
 
	for(int w = 1; w <= W; w++) {
		for(int h = 1; h <= H; h++) {
			int &ret = dp[w][h];
			ret = (ll(ds[w-1][h-1]) * w % MOD * 4 + ret) % MOD;
			if(1 < h) ret = (ll(dks[w-1][h-2]) * w + ret) % MOD;
			if(1 < w) ret = (ll(w) * (w-1) / 2 % MOD * ds[w-2][h-1] + ret) % MOD;
			ret = (ret + 1) % MOD;
		}
		ds[w][0] = 1; for(int j = 1; j <= H; j++) ds[w][j] = (ds[w][j-1] + dp[w][j]) % MOD;
		dks[w][0] = 1; for(int j = 1; j <= H; j++) dks[w][j] = (ll(dp[w][j]) * (j+1) + dks[w][j-1]) % MOD;
	}
 
	cout << ((dp[W][H] - 1 + MOD) % MOD) << endl;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...