답안 #134028

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
134028	2019-07-22T00:21:33 Z	tutis	Tents (JOI18_tents)	C++17	48 / 100	2000 ms	57812 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;
map<pair<ll, ll>, ll>M;
ll f(ll w, ll h)
{
	if (w > h)
		swap(w, h);
	if (M.count({w, h}))
		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	416 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	13 ms	1196 KB	Output is correct
6	Correct	14 ms	1276 KB	Output is correct
7	Correct	14 ms	1184 KB	Output is correct
8	Correct	12 ms	1036 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	27 ms	1912 KB	Output is correct
11	Correct	3 ms	504 KB	Output is correct
12	Correct	26 ms	1756 KB	Output is correct

Subtask #2

0 / 52.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	416 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	13 ms	1196 KB	Output is correct
6	Correct	14 ms	1276 KB	Output is correct
7	Correct	14 ms	1184 KB	Output is correct
8	Correct	12 ms	1036 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	27 ms	1912 KB	Output is correct
11	Correct	3 ms	504 KB	Output is correct
12	Correct	26 ms	1756 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	3 ms	760 KB	Output is correct
15	Execution timed out	2025 ms	57812 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-