Submission #305618

#	Time	Username	Problem	Language	Result	Execution time	Memory
305618		youngyojun	Tents (JOI18_tents)	C++17	100 / 100	305 ms	106232 KiB

tents

#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;
}

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