Submission #306953

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
306953	2020-09-26T15:08:25 Z	vipghn2003	Tents (JOI18_tents)	C++14	100 / 100	119 ms	70920 KB

tents

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=3005;
const int mod=1e9+7;
int n,m,dp[N][N];

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for(int j=0;j<=m;j++) dp[0][j]=1;
    for(int j=0;j<=n;j++) dp[j][0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            dp[i][j]=(dp[i-1][j]+dp[i-1][j-1]*j*4)%mod;
            if(j>=2) dp[i][j]=(dp[i][j]+dp[i-1][j-2]*j*(j-1)/2)%mod;
            if(i>=2) dp[i][j]=(dp[i][j]+dp[i-2][j-1]*j*(i-1))%mod;
        }
    }
    cout<<(dp[n][m]-1+mod)%mod;
}

Compilation message

tents.cpp:9:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    9 | main()
      |      ^

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	1 ms	512 KB	Output is correct
4	Correct	1 ms	1152 KB	Output is correct
5	Correct	1 ms	768 KB	Output is correct
6	Correct	1 ms	1408 KB	Output is correct
7	Correct	1 ms	896 KB	Output is correct
8	Correct	1 ms	1536 KB	Output is correct
9	Correct	1 ms	896 KB	Output is correct
10	Correct	2 ms	1792 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	3 ms	2304 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	1 ms	512 KB	Output is correct
4	Correct	1 ms	1152 KB	Output is correct
5	Correct	1 ms	768 KB	Output is correct
6	Correct	1 ms	1408 KB	Output is correct
7	Correct	1 ms	896 KB	Output is correct
8	Correct	1 ms	1536 KB	Output is correct
9	Correct	1 ms	896 KB	Output is correct
10	Correct	2 ms	1792 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	3 ms	2304 KB	Output is correct
13	Correct	1 ms	384 KB	Output is correct
14	Correct	6 ms	9728 KB	Output is correct
15	Correct	86 ms	55164 KB	Output is correct
16	Correct	7 ms	4224 KB	Output is correct
17	Correct	19 ms	12920 KB	Output is correct
18	Correct	23 ms	17152 KB	Output is correct
19	Correct	93 ms	62968 KB	Output is correct
20	Correct	74 ms	50936 KB	Output is correct
21	Correct	49 ms	33784 KB	Output is correct
22	Correct	49 ms	35448 KB	Output is correct
23	Correct	32 ms	27136 KB	Output is correct
24	Correct	119 ms	70920 KB	Output is correct
25	Correct	99 ms	61304 KB	Output is correct
26	Correct	105 ms	66624 KB	Output is correct
27	Correct	114 ms	68984 KB	Output is correct