oj.uz

답안 #819192

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
819192 2023-08-10T08:22:10 Z Alan 마스코트 (JOI13_mascots) C++17
100 / 100
 206 ms 183548 KB 
#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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 116940 KB Output is correct
2 Correct 80 ms 117028 KB Output is correct
3 Correct 82 ms 116956 KB Output is correct
4 Correct 86 ms 117028 KB Output is correct
5 Correct 84 ms 116972 KB Output is correct
6 Correct 82 ms 116964 KB Output is correct
7 Correct 82 ms 116968 KB Output is correct
8 Correct 83 ms 116924 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 116976 KB Output is correct
2 Correct 81 ms 116972 KB Output is correct
3 Correct 78 ms 117048 KB Output is correct
4 Correct 78 ms 117080 KB Output is correct
5 Correct 80 ms 117156 KB Output is correct
6 Correct 81 ms 117028 KB Output is correct
7 Correct 80 ms 116964 KB Output is correct
8 Correct 79 ms 117036 KB Output is correct
9 Correct 87 ms 117144 KB Output is correct
10 Correct 82 ms 117068 KB Output is correct
11 Correct 82 ms 117040 KB Output is correct
12 Correct 85 ms 116996 KB Output is correct

Subtask #3
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 117008 KB Output is correct
2 Correct 82 ms 117476 KB Output is correct
3 Correct 83 ms 118476 KB Output is correct
4 Correct 91 ms 126076 KB Output is correct
5 Correct 89 ms 124748 KB Output is correct
6 Correct 115 ms 122936 KB Output is correct
7 Correct 81 ms 118548 KB Output is correct
8 Correct 80 ms 117096 KB Output is correct
9 Correct 101 ms 117568 KB Output is correct
10 Correct 162 ms 183208 KB Output is correct
11 Correct 132 ms 161608 KB Output is correct
12 Correct 109 ms 117704 KB Output is correct
13 Correct 81 ms 119016 KB Output is correct
14 Correct 87 ms 117044 KB Output is correct
15 Correct 186 ms 183548 KB Output is correct
16 Correct 158 ms 166608 KB Output is correct
17 Correct 103 ms 121920 KB Output is correct
18 Correct 206 ms 180604 KB Output is correct