답안 #134029

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
134029	2019-07-22T00:22:23 Z	tutis	Tents (JOI18_tents)	C++17	100 / 100	175 ms	31324 KB

tents

/*input
4 3
*/
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll modulo = 1000000007;
ll M[3030][3030];
ll f(ll w, ll h)
{
	if (w > h)
		swap(w, h);
	if (M[w][h] != 0)
		return M[w][h];
	if (w == 0)
		return 1;
	if (w == 1)
		return h * (h - 1) / 2 + 4 * h + 1;
	ll ret = f(w, h - 1);
	ret += f(w - 2, h - 1) * ((w) * (w - 1) / 2);
	ret %= modulo;
	ret += f(w - 1, h - 1) * w * 4;
	ret %= modulo;
	ret += f(w - 1, h - 2) * w * (h - 1);
	ret %= modulo;
	return M[w][h] = ret;
}
int main()
{
	ios_base::sync_with_stdio(false);
	ll w, h;
	cin >> w >> h;
	cout << (f(w, h) + modulo - 1) % modulo << "\n";
}

Subtask #1

48.0 / 48.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	348 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	3 ms	760 KB	Output is correct
6	Correct	3 ms	760 KB	Output is correct
7	Correct	3 ms	892 KB	Output is correct
8	Correct	3 ms	632 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	4 ms	1144 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	4 ms	1784 KB	Output is correct

Subtask #2

52.0 / 52.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	348 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	3 ms	760 KB	Output is correct
6	Correct	3 ms	760 KB	Output is correct
7	Correct	3 ms	892 KB	Output is correct
8	Correct	3 ms	632 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	4 ms	1144 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	4 ms	1784 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	504 KB	Output is correct
15	Correct	164 ms	28580 KB	Output is correct
16	Correct	15 ms	3832 KB	Output is correct
17	Correct	51 ms	10232 KB	Output is correct
18	Correct	34 ms	9464 KB	Output is correct
19	Correct	175 ms	31324 KB	Output is correct
20	Correct	118 ms	23544 KB	Output is correct
21	Correct	83 ms	18176 KB	Output is correct
22	Correct	89 ms	18988 KB	Output is correct
23	Correct	71 ms	15224 KB	Output is correct
24	Correct	168 ms	30604 KB	Output is correct
25	Correct	122 ms	24312 KB	Output is correct
26	Correct	148 ms	28312 KB	Output is correct
27	Correct	173 ms	30252 KB	Output is correct