oj.uz

Submission #320089

# Submission time Handle Problem Language Result Execution time Memory
320089 2020-11-07T13:54:40 Z keta_tsimakuridze Tents (JOI18_tents) C++14
100 / 100
 177 ms 71268 KB 
#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.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 1004 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 1132 KB Output is correct
5 Correct 2 ms 1516 KB Output is correct
6 Correct 2 ms 1388 KB Output is correct
7 Correct 2 ms 1516 KB Output is correct
8 Correct 1 ms 1516 KB Output is correct
9 Correct 1 ms 876 KB Output is correct
10 Correct 3 ms 1772 KB Output is correct
11 Correct 1 ms 1516 KB Output is correct
12 Correct 3 ms 2284 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 1004 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 1132 KB Output is correct
5 Correct 2 ms 1516 KB Output is correct
6 Correct 2 ms 1388 KB Output is correct
7 Correct 2 ms 1516 KB Output is correct
8 Correct 1 ms 1516 KB Output is correct
9 Correct 1 ms 876 KB Output is correct
10 Correct 3 ms 1772 KB Output is correct
11 Correct 1 ms 1516 KB Output is correct
12 Correct 3 ms 2284 KB Output is correct
13 Correct 5 ms 7788 KB Output is correct
14 Correct 6 ms 9708 KB Output is correct
15 Correct 120 ms 55140 KB Output is correct
16 Correct 11 ms 9600 KB Output is correct
17 Correct 29 ms 17380 KB Output is correct
18 Correct 34 ms 17892 KB Output is correct
19 Correct 134 ms 62948 KB Output is correct
20 Correct 107 ms 50916 KB Output is correct
21 Correct 74 ms 35556 KB Output is correct
22 Correct 72 ms 35428 KB Output is correct
23 Correct 43 ms 27108 KB Output is correct
24 Correct 177 ms 71268 KB Output is correct
25 Correct 136 ms 61284 KB Output is correct
26 Correct 156 ms 66788 KB Output is correct
27 Correct 177 ms 69348 KB Output is correct