Submission #49241

#	Time	Username	Problem	Language	Result	Execution time	Memory
49241		spencercompton	Tents (JOI18_tents)	C++17	100 / 100	718 ms	71456 KiB

tents

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[3001][3001];
ll mod = 1000000007LL;
ll go(int rows, int cols){
	if(rows==0 || cols==0){
		return 1LL;
	}
	if(dp[rows][cols]!=-1){
		return dp[rows][cols];
	}
	ll ret = go(rows-1,cols);
	if(cols>=2){
		ret += ((ll)cols*(ll)(cols-1))/2LL*go(rows-1,cols-2);
		ret %= mod;
	}
	if(rows>=2){
		ret += (ll)cols*(ll)(rows-1)*go(rows-2,cols-1);
		ret %= mod;
	}
	ret += 4LL*(ll)cols*go(rows-1,cols-1);
	ret %= mod;
	dp[rows][cols] = ret;
	return ret;
}
int main(){
	for(int a = 0; a<=3000; a++){
		for(int b =0; b<=3000; b++){
			dp[a][b] = -1;
		}
	}
	int r, c;
	cin >> r >> c;
	cout << (go(r,c)+mod-1LL)%mod << endl;
}

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