Submission #1032103

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1032103	2024-07-23T11:28:09 Z	juicy	Tents (JOI18_tents)	C++17	100 / 100	240 ms	35932 KB

tents

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int MD = 1e9 + 7;

int F[3001][3001];

int add(int x, int y) {
	if ((x += y) >= MD) {
		x -= MD;
	}
	if (x < 0) {
		x += MD;
	}
	return x;
}

int C2(int N) {
	return N * (N - 1) / 2;
}

int dp(int i, int j) {
	if (i < 0 || j < 0) {
		return 0;
	}
	if (i == 0) {
		return 1;
	}
	if (~F[i][j]) {
		return F[i][j];
	}
	int &res = F[i][j];
	res = 0;
	res = add(res, dp(i - 1, j));
	res = add(res, (long long) dp(i - 1, j - 2) * C2(j) % MD);
	res = add(res, (long long) dp(i - 1, j - 1) * 4 % MD * j % MD);
	res = add(res, (long long) dp(i - 2, j - 1) * (i - 1) % MD * j % MD);
	return res;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	int N, M; cin >> N >> M;
	memset(F, -1, sizeof(F));
	cout << add(dp(N, M), -1);
	return 0;
}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	35676 KB	Output is correct
2	Correct	8 ms	35480 KB	Output is correct
3	Correct	9 ms	35536 KB	Output is correct
4	Correct	9 ms	35672 KB	Output is correct
5	Correct	10 ms	35476 KB	Output is correct
6	Correct	9 ms	35720 KB	Output is correct
7	Correct	8 ms	35676 KB	Output is correct
8	Correct	10 ms	35676 KB	Output is correct
9	Correct	8 ms	35676 KB	Output is correct
10	Correct	10 ms	35672 KB	Output is correct
11	Correct	8 ms	35676 KB	Output is correct
12	Correct	11 ms	35676 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	35676 KB	Output is correct
2	Correct	8 ms	35480 KB	Output is correct
3	Correct	9 ms	35536 KB	Output is correct
4	Correct	9 ms	35672 KB	Output is correct
5	Correct	10 ms	35476 KB	Output is correct
6	Correct	9 ms	35720 KB	Output is correct
7	Correct	8 ms	35676 KB	Output is correct
8	Correct	10 ms	35676 KB	Output is correct
9	Correct	8 ms	35676 KB	Output is correct
10	Correct	10 ms	35672 KB	Output is correct
11	Correct	8 ms	35676 KB	Output is correct
12	Correct	11 ms	35676 KB	Output is correct
13	Correct	8 ms	35676 KB	Output is correct
14	Correct	8 ms	35676 KB	Output is correct
15	Correct	166 ms	35676 KB	Output is correct
16	Correct	12 ms	35672 KB	Output is correct
17	Correct	25 ms	35736 KB	Output is correct
18	Correct	48 ms	35676 KB	Output is correct
19	Correct	184 ms	35672 KB	Output is correct
20	Correct	157 ms	35672 KB	Output is correct
21	Correct	87 ms	35672 KB	Output is correct
22	Correct	99 ms	35676 KB	Output is correct
23	Correct	72 ms	35932 KB	Output is correct
24	Correct	240 ms	35912 KB	Output is correct
25	Correct	189 ms	35676 KB	Output is correct
26	Correct	207 ms	35676 KB	Output is correct
27	Correct	228 ms	35672 KB	Output is correct