Submission #320089

#	Time	Username	Problem	Language	Result	Execution time	Memory
320089		keta_tsimakuridze	Tents (JOI18_tents)	C++14	100 / 100	177 ms	71268 KiB

tents

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
long long n,m,k,i,dp[3005][3005];
int main(){
	cin>>n>>m;
	dp[0][0]=1;
	for(k=1;k<=max(n,m);k++)
	dp[k][0]=dp[0][k]=1;
	for(k=1;k<=n;k++){	
	for(i=1;i<=m;i++){
		dp[k][i]=dp[k-1][i];
		if(i>=2) dp[k][i]+=dp[k-1][i-2]%mod*(i*(i-1))/2%mod;
		dp[k][i]+=4*i*dp[k-1][i-1]%mod;
		if(k>=2) dp[k][i]+=dp[k-2][i-1]%mod*i%mod*(k-1)%mod;
		dp[k][i]%=mod;
	//	cout<<k<<" "<<i<<" "<<dp[k][i]<<endl;
	
	} }
	cout<<(dp[n][m]-1+mod)%mod;
}

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