Submission #34119

#	Time	Username	Problem	Language	Result	Execution time	Memory
34119		natsukagami	마스코트 (JOI13_mascots)	C++14	100 / 100	319 ms	108216 KiB

mascots

#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 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60