oj.uz

Submission #529026

# Submission time Handle Problem Language Result Execution time Memory
529026 2022-02-22T02:31:20 Z fhvirus Tents (JOI18_tents) C++17
48 / 100
 2000 ms 24052 KB 
#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll; typedef pair<int, int> pii;
#define pb emplace_back
#define AI(x) begin(x),end(x)
#define ff first
#define ss second
#ifdef OWO
#define debug(args...) LKJ("\033[0;32m[ " + string(#args) + " ]\033[0m", args)
template <class I> void LKJ(I&&x) { cerr << x << endl; }
template <class I, class...T> void LKJ(I&&x, T&&...t) { cerr << x << ", "; LKJ(t...); }
template <class I> void OI(I a, I b) { while (a < b) cerr << *a << " \n"[next(a) == b]; }
#else
#define debug(...) 0
#define OI(...) 0
#endif

const int MOD = 1'000'000'007;
int mad(int u, int v) {
	u += v - MOD;
	u += MOD & (u >> 31);
	return u;
}
int mul(int u, int v) {
	return (ll) u * v % MOD;
}
int mow(int x, int e) {
	int r = 1;
	while (e) {
		if (e & 1) r = mul(r, x);
		x = mul(x, x);
		e >>= 1;
	}
	return r;
}

const int kN = 3003;
int fac[kN], caf[kN], inv[kN];
void init(int n) {
	fac[0] = 1;
	for (int i = 1; i <= n; ++i) fac[i] = mul(fac[i - 1], i);
	caf[n] = mow(fac[n], MOD - 2);
	for (int i = n; i >= 1; --i) caf[i - 1] = mul(caf[i], i);
	for (int i = 1; i <= n; ++i) inv[i] = mul(fac[i - 1], caf[i]);
}
int C(int n, int k) {
	if (0 > k or k > n) return 0;
	return mul(fac[n], mul(caf[k], caf[n - k]));
}
int P(int n, int k) {
	if (0 > k or k > n) return 0;
	return mul(fac[n], caf[n - k]);
}

int H, W, ans;
int tmp[kN][kN];

int solve(int n, int m) {
	if (n > m) swap(n, m);
	if (tmp[n][m] != -1) return tmp[n][m];
	tmp[n][m] = 0;
	for (int i = 0; i <= n; ++i)
		tmp[n][m] = mad(tmp[n][m], mul(mul(C(n, i), P(m, i)), mow(4, i)));
	return tmp[n][m];
}

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

	cin >> H >> W;
	if (H > W) swap(H, W);
	init(max(H, W));

	for (int i = 0; i <= H; ++i)
		for (int j = 0; j <= W; ++j)
			tmp[i][j] = -1;

	for (int r = 0; r <= H and 2 * r <= W; ++r)
		for (int c = 0; r + 2 * c <= H and 2 * r + c <= W; ++c) {
			int v = mul(C(H, r), mul(P(W, 2 * r), mow(inv[2], r)));
			v = mul(v, mul(C(W - 2 * r, c), mul(P(H - r, 2 * c), mow(inv[2], c))));
			v = mul(v, solve(H - (r + 2 * c), W - (2 * r + c)));
			ans = mad(ans, v);
		}

	cout << mad(ans, MOD - 1) << '\n';

	return 0;
}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 3 ms 716 KB Output is correct
7 Correct 3 ms 716 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 9 ms 960 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 30 ms 1884 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 3 ms 716 KB Output is correct
7 Correct 3 ms 716 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 9 ms 960 KB Output is correct
11 Correct 1 ms 328 KB Output is correct
12 Correct 30 ms 1884 KB Output is correct
13 Correct 1 ms 320 KB Output is correct
14 Correct 1 ms 324 KB Output is correct
15 Execution timed out 2088 ms 24052 KB Time limit exceeded
16 Halted 0 ms 0 KB -