oj.uz

Submission #34119

# Submission time Handle Problem Language Result Execution time Memory
34119 2017-11-07T15:30:33 Z natsukagami 마스코트 (JOI13_mascots) C++14
100 / 100
 319 ms 108216 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 3005;
const int mod = 1e9 + 7;

int R, C, N;
int minX = 1e9, maxX = -1e9, minY = 1e9, maxY = -1e9;

int ft[maxn * maxn];
int bc[maxn][maxn];

int f[maxn][maxn];

int cal(int x, int y) {
	if (f[x][y]) return f[x][y];
	if (x == R && y == C) return 1;
	if (x < R)
		f[x][y] = (f[x][y] + cal(x + 1, y) * 1LL * ft[y]) % mod;
	if (y < C)
		f[x][y] = (f[x][y] + cal(x, y + 1) * 1LL * ft[x]) % mod;
	return f[x][y];
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> R >> C;
	ft[0] = 1;
	for (int i = 1; i <= R * C; ++i) 
		ft[i] = ft[i - 1] * 1LL * i % mod;
	bc[0][0] = 1;
	for (int i = 1; i <= 3000; ++i) {
		bc[0][i] = 1;
		for (int j = 1; j <= i; ++j)
			bc[j][i] = (bc[j][i - 1] + bc[j - 1][i - 1]) % mod;
	}
	cin >> N;
	for (int i = 1; i <= N; ++i) {
		int x, y; cin >> x >> y;
		minX = min(minX, x); maxX = max(maxX, x);
		minY = min(minY, y); maxY = max(maxY, y);
	}
	int ans = ft[(maxX - minX + 1) * (maxY - minY + 1) - N];
	ans = ans * 1LL * cal(maxX - minX + 1, maxY - minY + 1) % mod;
	ans = ans * 1LL * bc[minX - 1][R - maxX + minX - 1] % mod * bc[minY - 1][C - maxY + minY - 1] % mod;
	cout << ans << endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 107996 KB Output is correct
2 Correct 133 ms 107996 KB Output is correct
3 Correct 113 ms 107996 KB Output is correct
4 Correct 123 ms 107996 KB Output is correct
5 Correct 106 ms 107996 KB Output is correct
6 Correct 123 ms 107996 KB Output is correct
7 Correct 123 ms 107996 KB Output is correct
8 Correct 129 ms 107996 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 107996 KB Output is correct
2 Correct 129 ms 107996 KB Output is correct
3 Correct 123 ms 107996 KB Output is correct
4 Correct 103 ms 107996 KB Output is correct
5 Correct 96 ms 107996 KB Output is correct
6 Correct 113 ms 107996 KB Output is correct
7 Correct 99 ms 107996 KB Output is correct
8 Correct 113 ms 107996 KB Output is correct
9 Correct 113 ms 107996 KB Output is correct
10 Correct 99 ms 107996 KB Output is correct
11 Correct 109 ms 107996 KB Output is correct
12 Correct 119 ms 107996 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 107996 KB Output is correct
2 Correct 106 ms 107996 KB Output is correct
3 Correct 119 ms 107996 KB Output is correct
4 Correct 133 ms 107996 KB Output is correct
5 Correct 143 ms 107996 KB Output is correct
6 Correct 139 ms 107996 KB Output is correct
7 Correct 119 ms 107996 KB Output is correct
8 Correct 136 ms 107996 KB Output is correct
9 Correct 193 ms 107996 KB Output is correct
10 Correct 313 ms 108216 KB Output is correct
11 Correct 249 ms 108148 KB Output is correct
12 Correct 186 ms 107996 KB Output is correct
13 Correct 119 ms 107996 KB Output is correct
14 Correct 169 ms 107996 KB Output is correct
15 Correct 303 ms 108212 KB Output is correct
16 Correct 266 ms 108176 KB Output is correct
17 Correct 179 ms 107996 KB Output is correct
18 Correct 319 ms 108204 KB Output is correct