Submission #963534

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
963534	2024-04-15T09:29:04 Z	oblantis	Tents (JOI18_tents)	C++17	100 / 100	210 ms	58852 KB

tents

//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
#define uid(a, b) uniform_int_distribution<int>(a, b)(mt)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 2e8+1;
const int mod = 1e9+7;
const int maxn = 3000 + 5;
mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
ll wt[maxn][maxn];
ll go(int n, int m){
    if(n < 0 || m < 0)return 0;
    if(n == 0)return 1;
    if(wt[n][m])return wt[n][m];
    wt[n][m] = (go(n - 1, m) + go(n - 1, m - 1) * 4 * m + go(n - 1, m - 2) * m * (m - 1) / 2 + go(n - 2, m - 1) * m * (n - 1)) % mod;
    return wt[n][m];
}
void solve() {
    int n, m;
    cin >> n >> m;
    cout << go(n, m) - 1;
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int times = 1; //cin >> times;
	for(int i = 1; i <= times; i++) {
		solve();
	}
	return 0;
}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	604 KB	Output is correct
4	Correct	1 ms	1116 KB	Output is correct
5	Correct	1 ms	604 KB	Output is correct
6	Correct	1 ms	1380 KB	Output is correct
7	Correct	1 ms	864 KB	Output is correct
8	Correct	1 ms	1376 KB	Output is correct
9	Correct	1 ms	836 KB	Output is correct
10	Correct	2 ms	1884 KB	Output is correct
11	Correct	1 ms	500 KB	Output is correct
12	Correct	2 ms	2140 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	604 KB	Output is correct
4	Correct	1 ms	1116 KB	Output is correct
5	Correct	1 ms	604 KB	Output is correct
6	Correct	1 ms	1380 KB	Output is correct
7	Correct	1 ms	864 KB	Output is correct
8	Correct	1 ms	1376 KB	Output is correct
9	Correct	1 ms	836 KB	Output is correct
10	Correct	2 ms	1884 KB	Output is correct
11	Correct	1 ms	500 KB	Output is correct
12	Correct	2 ms	2140 KB	Output is correct
13	Correct	1 ms	352 KB	Output is correct
14	Correct	5 ms	9940 KB	Output is correct
15	Correct	121 ms	47456 KB	Output is correct
16	Correct	3 ms	1628 KB	Output is correct
17	Correct	12 ms	6860 KB	Output is correct
18	Correct	28 ms	13684 KB	Output is correct
19	Correct	135 ms	53332 KB	Output is correct
20	Correct	101 ms	42328 KB	Output is correct
21	Correct	56 ms	25436 KB	Output is correct
22	Correct	68 ms	30800 KB	Output is correct
23	Correct	45 ms	26496 KB	Output is correct
24	Correct	210 ms	58852 KB	Output is correct
25	Correct	126 ms	49236 KB	Output is correct
26	Correct	149 ms	54820 KB	Output is correct
27	Correct	182 ms	57172 KB	Output is correct