Submission #134028

# Submission time Handle Problem Language Result Execution time Memory
134028 2019-07-22T00:21:33 Z tutis Tents (JOI18_tents) C++17
48 / 100
2000 ms 57812 KB
/*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";
}
# Verdict Execution time Memory 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
# Verdict Execution time Memory 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 -