Submission #73150

#	Time	Username	Problem	Language	Result	Execution time	Memory
73150		KLPP	Tents (JOI18_tents)	C++14	100 / 100	564 ms	282896 KiB

tents

#include<iostream>

using namespace std;
#define MOD 1000000007
typedef long long int lld;
lld DP[6000][6000];

lld trabalha(int x, int y){
	if(x<0 || y<0)return 0;
	if(DP[x][y]!=-1)return DP[x][y];
	lld ans=0;
	ans+=trabalha(x-1,y);
	ans%=MOD;
	ans+=4*y*trabalha(x-1,y-1);
	ans%=MOD;
	lld comb=y*(y-1);
	comb/=2;
	comb%=MOD;
	//cout<<ans<<endl;
	ans+=comb*trabalha(x-1,y-2);
	comb=y*(x-1);
	comb%=MOD;
	//cout<<ans<<endl;
	ans+=comb*trabalha(x-2,y-1);
	ans%=MOD;
	DP[x][y]=ans;
	return ans;
}
int main(){
	for(int i=0;i<6000;i++){
		for(int j=0;j<6000;j++){
			DP[i][j]=-1;
			if(i==0 || j==0)DP[i][j]=1;
		}
	}
	
	int x,y;
	cin>>x>>y;
	cout<<(trabalha(x,y)+MOD-1)%MOD<<endl;
	/*for(int i=0;i<=x;i++){
		for(int j=0;j<=y;j++){
			cout<<i<<" "<<j<<" "<<DP[i][j]<<endl;
		}
	}*/
	return 0;
}

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