Submission #483628

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
483628	2021-10-31T10:56:04 Z	ymm	Tents (JOI18_tents)	C++17	100 / 100	92 ms	71408 KB

tents

///
///   You fell for it, fool!
///   Thunder Cross Split Attack!
///

#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
typedef long long ll;
using namespace std;

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

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	Loop(i,0,N) dp[0][i] = dp[i][0] = 1;
	Loop(x,1,N) Loop(y,1,N)
	{
		dp[x][y] = dp[x-1][y];
		dp[x][y] += 4*y*dp[x-1][y-1] % mod;
		if(y>1) dp[x][y] += y*(y-1)/2*dp[x-1][y-2] % mod;
		if(x>1) dp[x][y] += y*(x-1)*dp[x-2][y-1] % mod;
		dp[x][y] %= mod;
	}
	cout << (dp[n][m]+mod-1)%mod << '\n';
}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	84 ms	71288 KB	Output is correct
2	Correct	87 ms	71184 KB	Output is correct
3	Correct	86 ms	71108 KB	Output is correct
4	Correct	85 ms	71188 KB	Output is correct
5	Correct	87 ms	71260 KB	Output is correct
6	Correct	84 ms	71192 KB	Output is correct
7	Correct	86 ms	71196 KB	Output is correct
8	Correct	87 ms	71196 KB	Output is correct
9	Correct	86 ms	71164 KB	Output is correct
10	Correct	85 ms	71128 KB	Output is correct
11	Correct	86 ms	71408 KB	Output is correct
12	Correct	84 ms	71128 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	84 ms	71288 KB	Output is correct
2	Correct	87 ms	71184 KB	Output is correct
3	Correct	86 ms	71108 KB	Output is correct
4	Correct	85 ms	71188 KB	Output is correct
5	Correct	87 ms	71260 KB	Output is correct
6	Correct	84 ms	71192 KB	Output is correct
7	Correct	86 ms	71196 KB	Output is correct
8	Correct	87 ms	71196 KB	Output is correct
9	Correct	86 ms	71164 KB	Output is correct
10	Correct	85 ms	71128 KB	Output is correct
11	Correct	86 ms	71408 KB	Output is correct
12	Correct	84 ms	71128 KB	Output is correct
13	Correct	87 ms	71224 KB	Output is correct
14	Correct	86 ms	71108 KB	Output is correct
15	Correct	85 ms	71144 KB	Output is correct
16	Correct	92 ms	71328 KB	Output is correct
17	Correct	85 ms	71116 KB	Output is correct
18	Correct	87 ms	71128 KB	Output is correct
19	Correct	85 ms	71104 KB	Output is correct
20	Correct	87 ms	71160 KB	Output is correct
21	Correct	85 ms	71112 KB	Output is correct
22	Correct	90 ms	71236 KB	Output is correct
23	Correct	85 ms	71108 KB	Output is correct
24	Correct	86 ms	71204 KB	Output is correct
25	Correct	87 ms	71212 KB	Output is correct
26	Correct	89 ms	71188 KB	Output is correct
27	Correct	85 ms	71208 KB	Output is correct