| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 819192 |
2023-08-10T08:22:10 Z |
Alan |
마스코트 (JOI13_mascots) |
C++17 |
|
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;
}
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
