Submission #485263

#	Time	Username	Problem	Language	Result	Execution time	Memory
485263		CSQ31	Tents (JOI18_tents)	C++17	100 / 100	337 ms	71000 KiB

tents

#include <bits/stdc++.h>
using namespace std;
#define MOD (ll)(1e9+7)
typedef long long int ll;
//each row <=2
//each col <=2
//cant have triangle
inline void mod(ll &x){
	if(x>=MOD)x-=MOD;
}
ll eval(ll x){
	return (x*(x-1))/2 %MOD;
}
ll dp[3001][3001];
ll solve(int h,int w){
	if(dp[h][w]!=-1)return dp[h][w];
	if(!h || !w)return 1;
	ll res = solve(h-1,w); //empty row
	res+=(solve(h-1,w-1) * 4LL * w %MOD); //single tent in a col
	mod(res);
	if(w>=2)res+=solve(h-1,w-2) * eval(w) %MOD;//two tents same row
	mod(res);
	if(h>=2)res+=(solve(h-2,w-1) * (h-1) %MOD) * w%MOD; //two tents same col
	mod(res);
	dp[h][w] = res;
	//cout<<h<<" "<<w<<" "<<res<<'\n';
	return res;
}
int main()
{
	int h,w;
	cin>>h>>w;
	for(int i=0;i<=h;i++)
		for(int j=0;j<=w;j++)dp[i][j] = -1;
		
	cout<<(solve(h,w)+MOD-1)%MOD;
}

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