Submission #335384

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
335384	2020-12-12T08:09:01 Z	mehrdad_sohrabi	Tents (JOI18_tents)	C++14	100 / 100	312 ms	73580 KB

tents

#include <bits/stdc++.h>
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
#define endl '\n'
#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
using namespace std;
const int N=3e3+100;
ll dp[N][N];
ll mod=1e9+7;
int32_t main(){
    ll n,m;
    cin >> n >> m;
    dp[0][0]=1;
    for (int i=1;i<N;i++) dp[0][i]=1,dp[i][0]=1;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            dp[i][j]=dp[i][j-1]+dp[i-1][j-1]*4*i%mod;
            if (i>=2) dp[i][j]+=dp[i-2][j-1]*(i*(i-1)/2)%mod;
            if (j>=2) dp[i][j]+=dp[i-1][j-2]*i*(j-1)%mod;
            dp[i][j]%=mod;
        }
    }
    cout << dp[n][m]-1 << endl;

}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	12928 KB	Output is correct
2	Correct	7 ms	12908 KB	Output is correct
3	Correct	8 ms	12908 KB	Output is correct
4	Correct	7 ms	12908 KB	Output is correct
5	Correct	7 ms	13036 KB	Output is correct
6	Correct	7 ms	13036 KB	Output is correct
7	Correct	9 ms	13036 KB	Output is correct
8	Correct	7 ms	13036 KB	Output is correct
9	Correct	7 ms	12908 KB	Output is correct
10	Correct	10 ms	13164 KB	Output is correct
11	Correct	8 ms	13056 KB	Output is correct
12	Correct	10 ms	13564 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	12928 KB	Output is correct
2	Correct	7 ms	12908 KB	Output is correct
3	Correct	8 ms	12908 KB	Output is correct
4	Correct	7 ms	12908 KB	Output is correct
5	Correct	7 ms	13036 KB	Output is correct
6	Correct	7 ms	13036 KB	Output is correct
7	Correct	9 ms	13036 KB	Output is correct
8	Correct	7 ms	13036 KB	Output is correct
9	Correct	7 ms	12908 KB	Output is correct
10	Correct	10 ms	13164 KB	Output is correct
11	Correct	8 ms	13056 KB	Output is correct
12	Correct	10 ms	13564 KB	Output is correct
13	Correct	7 ms	12908 KB	Output is correct
14	Correct	8 ms	12908 KB	Output is correct
15	Correct	196 ms	56684 KB	Output is correct
16	Correct	18 ms	15724 KB	Output is correct
17	Correct	48 ms	22636 KB	Output is correct
18	Correct	58 ms	25088 KB	Output is correct
19	Correct	229 ms	63724 KB	Output is correct
20	Correct	183 ms	53752 KB	Output is correct
21	Correct	120 ms	39660 KB	Output is correct
22	Correct	120 ms	39276 KB	Output is correct
23	Correct	70 ms	27500 KB	Output is correct
24	Correct	312 ms	73580 KB	Output is correct
25	Correct	231 ms	64876 KB	Output is correct
26	Correct	271 ms	69868 KB	Output is correct
27	Correct	302 ms	71920 KB	Output is correct