Submission #819192

#	Time	Username	Problem	Language	Result	Execution time	Memory
819192		Alan	마스코트 (JOI13_mascots)	C++17	100 / 100	206 ms	183548 KiB

mascots

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll mod = 1e9+7;
ll fac[9000001], ncr[3001][3001], dp[3001][3001];

int main () {
	fac[0] = ncr[0][0] = 1;
	for (int i = 1; i <= 9000000; i++) fac[i] = (fac[i-1] * i) % mod;
	for (int i = 1; i <= 3000; i++) {
		ncr[i][0] = ncr[i][i] = 1;
		for (int j = 1; j < i; j++) ncr[i][j] = (ncr[i-1][j-1] + ncr[i-1][j]) % mod;
	}
	int r, c, n;
	cin >> r >> c >> n;
	int r1 = r, r2 = 1, c1 = c, c2 = 1;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		r1 = min(r1, a);
		r2 = max(r2, a);
		c1 = min(c1, b);
		c2 = max(c2, b);
	}
	r2 -= r1-1;
	c2 -= c1-1;
	dp[r2][c2] = fac[r2 * c2 - n];
	for (int i = r2; i <= r; i++) for (int j = c2; j <= c; j++) if (!dp[i][j]) dp[i][j] = (dp[i-1][j] * fac[j] + dp[i][j-1] * fac[i]) % mod;
	cout << dp[r][c] * ncr[r-r2][r1-1] % mod * ncr[c-c2][c1-1] % mod << '\n';
	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60