제출 #234433

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
234433		oolimry	Tents (JOI18_tents)	C++14	100 / 100	237 ms	71288 KiB

tents

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

int memo[3005][3005];

const int mod = 1000000007;
int dp(int H, int W){ ///ways such that the topmost row and rightmost column are occupied
	if(W < 0 || W < 0) return 0;
	if(W == 0 || H == 0) return 1;
	if(memo[H][W]  != -1) return memo[H][W];
	
	int ans = 0;
	if(H == 1){
		ans = 4*W + 1;
		ans += (W-1)*W/2;
		return ans;
	}
	
	///new row is empty
	ans += dp(H-1,W);
	
	///new row is 1 thing facing nothing
	ans += 4*dp(H-1,W-1)*W;
	
	///new row is 2 things facing each other
	ans += dp(H-1,W-2) * (W) * (W-1) / 2;
	
	///new row is south, and north is somwhere below
	ans += dp(H-2, W-1) * W * (H-1);
	
	ans %= mod;
	memo[H][W] = ans;
	return ans;
}

signed main(){	
	int H, W; cin >> H >> W;
	memset(memo, -1, sizeof(memo));
	
	int ans = dp(H,W);
	ans--;
	if(ans < 0) ans += mod;
	cout << ans;
}

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