Submission #100767

#	Time	Username	Problem	Language	Result	Execution time	Memory
100767		TAISA_	Tents (JOI18_tents)	C++14	48 / 100	879 ms	220792 KiB

tents

#include<bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
using namespace std;
using ll=long long;
const ll MOD=1000000007LL;
template<typename T> void chmax(T &a,T b){a=max(a,b);}
template<typename T> void chmin(T &a,T b){a=min(a,b);}
ll dp[310][310][310];
int main(){
	ll h,w;cin>>h>>w;if(h>300||w>300)return 0;
	dp[0][0][w]=1;
	for(ll i=1;i<=h;i++){
		for(ll j=0;j<=w;j++){
			for(ll k=0;k<=w;k++){
				if(j<w)dp[i][j][k]+=dp[i-1][j+1][k]*(j+1LL)%MOD;
				if(k<w){
					dp[i][j][k]+=dp[i-1][j][k+1]*4LL%MOD*(k+1LL)%MOD;
					if(j)dp[i][j][k]+=dp[i-1][j-1][k+1]*(k+1LL)%MOD;
					if(k<w-1)dp[i][j][k]+=dp[i-1][j][k+2]*((k+2LL)*(k+1LL)/2LL)%MOD;
				}
				dp[i][j][k]+=dp[i-1][j][k];
				dp[i][j][k]%=MOD;
			}
		}
	}
	ll ans=0;
	for(int k=0;k<w;k++){
		ans+=dp[h][0][k];
		ans%=MOD;
	}
	cout<<ans<<endl;
}

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