답안 #887745

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
887745	2023-12-15T07:15:29 Z	vjudge1	Tents (JOI18_tents)	C++17	100 / 100	63 ms	70980 KB

tents

#include <bits/stdc++.h>
#define pb push_back
#define dbg(x) cout << "reached here " << x << endl;
#define f first
#define s second
#define ll long long

using namespace std;
typedef pair<int, int> pii;

const int maxn = 3005, mod = 1e9+7;
ll dp[maxn][maxn];

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

	int h, w;
	cin >> h >> w;

	for (int i = 1; i <= h; ++i)
		dp[i][1] = 4*i + i*(i-1)/2;
	for (int i = 1; i <= w; ++i)
		dp[1][i] = 4*i + i*(i-1)/2;

	for (int i = 2; i <= h; ++i)
		for (int j = 2; j <= w; ++j)
			dp[i][j] = (dp[i][j-1] + (i*(i-1)/2)*(dp[i-2][j-1]+1) + i*(4*(dp[i-1][j-1]+1) + (j-1)*(dp[i-1][j-2]+1))) % mod;

	cout << dp[h][w] << endl;
		
	return 0;
} 

Subtask #1

48.0 / 48.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	6636 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	6492 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	6492 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	8540 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Correct	2 ms	8540 KB	Output is correct

Subtask #2

52.0 / 52.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	1 ms	6636 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	1 ms	6492 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	1 ms	6492 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	1 ms	8540 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Correct	2 ms	8540 KB	Output is correct
13	Correct	0 ms	348 KB	Output is correct
14	Correct	6 ms	55836 KB	Output is correct
15	Correct	42 ms	66240 KB	Output is correct
16	Correct	3 ms	6488 KB	Output is correct
17	Correct	10 ms	17000 KB	Output is correct
18	Correct	13 ms	29276 KB	Output is correct
19	Correct	48 ms	70488 KB	Output is correct
20	Correct	39 ms	57944 KB	Output is correct
21	Correct	26 ms	39512 KB	Output is correct
22	Correct	27 ms	51804 KB	Output is correct
23	Correct	20 ms	70416 KB	Output is correct
24	Correct	63 ms	70980 KB	Output is correct
25	Correct	48 ms	62044 KB	Output is correct
26	Correct	57 ms	68188 KB	Output is correct
27	Correct	61 ms	70236 KB	Output is correct