답안 #529119

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
529119	2022-02-22T07:32:26 Z	fhvirus	Tents (JOI18_tents)	C++17	100 / 100	44 ms	35476 KB

tents

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

const int kN = 3003;
const int MOD = 1e9 + 7;

int H, W;
int dp[kN][kN];

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> H >> W;
	for (int i = 0; i <= H; ++i) dp[i][0] = 1;
	for (int j = 0; j <= W; ++j) dp[0][j] = 1;

	for (int i = 1; i <= H; ++i)
		for (int j = 1; j <= W; ++j) {
			int64_t v = dp[i - 1][j];
			v += 4ll * j * dp[i - 1][j - 1];
			if (i >= 2) v += 1ll * dp[i - 2][j - 1] * (i - 1) * j;
			if (j >= 2) v += 1ll * dp[i - 1][j - 2] * j * (j - 1) / 2;
			dp[i][j] = v % MOD;
		}

	cout << (dp[H][W] + MOD - 1) % MOD << '\n';

	return 0;
}

Subtask #1

48.0 / 48.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	0 ms	460 KB	Output is correct
4	Correct	1 ms	1100 KB	Output is correct
5	Correct	1 ms	588 KB	Output is correct
6	Correct	1 ms	1228 KB	Output is correct
7	Correct	1 ms	716 KB	Output is correct
8	Correct	1 ms	1356 KB	Output is correct
9	Correct	0 ms	716 KB	Output is correct
10	Correct	1 ms	1612 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	1740 KB	Output is correct

Subtask #2

52.0 / 52.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	0 ms	460 KB	Output is correct
4	Correct	1 ms	1100 KB	Output is correct
5	Correct	1 ms	588 KB	Output is correct
6	Correct	1 ms	1228 KB	Output is correct
7	Correct	1 ms	716 KB	Output is correct
8	Correct	1 ms	1356 KB	Output is correct
9	Correct	0 ms	716 KB	Output is correct
10	Correct	1 ms	1612 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	1740 KB	Output is correct
13	Correct	0 ms	332 KB	Output is correct
14	Correct	4 ms	9548 KB	Output is correct
15	Correct	33 ms	32788 KB	Output is correct
16	Correct	3 ms	2636 KB	Output is correct
17	Correct	10 ms	7884 KB	Output is correct
18	Correct	10 ms	10956 KB	Output is correct
19	Correct	37 ms	34460 KB	Output is correct
20	Correct	30 ms	28996 KB	Output is correct
21	Correct	20 ms	19680 KB	Output is correct
22	Correct	27 ms	22216 KB	Output is correct
23	Correct	14 ms	19660 KB	Output is correct
24	Correct	44 ms	35476 KB	Output is correct
25	Correct	35 ms	30732 KB	Output is correct
26	Correct	40 ms	33348 KB	Output is correct
27	Correct	44 ms	34612 KB	Output is correct