Submission #100767

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
100767	2019-03-14T08:47:10 Z	TAISA_	Tents (JOI18_tents)	C++14	48 / 100	879 ms	220792 KB

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.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	5 ms	1280 KB	Output is correct
3	Correct	3 ms	640 KB	Output is correct
4	Correct	6 ms	2560 KB	Output is correct
5	Correct	157 ms	39216 KB	Output is correct
6	Correct	94 ms	49848 KB	Output is correct
7	Correct	155 ms	48816 KB	Output is correct
8	Correct	65 ms	37080 KB	Output is correct
9	Correct	5 ms	2176 KB	Output is correct
10	Correct	239 ms	99168 KB	Output is correct
11	Correct	37 ms	7680 KB	Output is correct
12	Correct	879 ms	220792 KB	Output is correct

Subtask #2

0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	5 ms	1280 KB	Output is correct
3	Correct	3 ms	640 KB	Output is correct
4	Correct	6 ms	2560 KB	Output is correct
5	Correct	157 ms	39216 KB	Output is correct
6	Correct	94 ms	49848 KB	Output is correct
7	Correct	155 ms	48816 KB	Output is correct
8	Correct	65 ms	37080 KB	Output is correct
9	Correct	5 ms	2176 KB	Output is correct
10	Correct	239 ms	99168 KB	Output is correct
11	Correct	37 ms	7680 KB	Output is correct
12	Correct	879 ms	220792 KB	Output is correct
13	Incorrect	2 ms	384 KB	Output isn't correct
14	Halted	0 ms	0 KB	-