oj.uz

Submission #417061

# Submission time Handle Problem Language Result Execution time Memory
417061 2021-06-03T11:17:33 Z proteam23 마스코트 (JOI13_mascots) C++14
100 / 100
 202 ms 96912 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int R = 3007;
const int MOD = 1e9 + 7;

int r, c, n, dp[R][R], fact[R * R], nCk[R][R];

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    fact[0] = 1;
    for(int i = 1; i < R * R; i++)
        fact[i] = (ll) fact[i - 1] * i % MOD;
    for(int i = 0; i < R; i++){
        nCk[i][0] = 1;
        for(int j = 1; j <= i; j++)
            nCk[i][j] = (nCk[i - 1][j] + nCk[i - 1][j - 1]) % MOD;
    }

    cin >> r >> c >> n;
    int minX = R, maxX = 0, minY = R, maxY = 0;
    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 r0 = maxX - minX + 1;
    int c0 = maxY - minY + 1;

    dp[r0][c0] = fact[r0 * c0 - n];
    for(int i = r0; i <= r; i++)
        for(int j = c0; j <= c; j++){
            if (i < r)
                dp[i + 1][j] = (dp[i + 1][j] + (ll) dp[i][j] * fact[j]) % MOD;
            if (j < c)
                dp[i][j + 1] = (dp[i][j + 1] + (ll) dp[i][j] * fact[i]) % MOD;
        }

    cout << (ll) dp[r][c] * nCk[r - r0][minX - 1] % MOD * nCk[c - c0][minY - 1] % MOD;
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 63268 KB Output is correct
2 Correct 85 ms 63164 KB Output is correct
3 Correct 82 ms 63272 KB Output is correct
4 Correct 83 ms 63268 KB Output is correct
5 Correct 84 ms 63236 KB Output is correct
6 Correct 84 ms 63172 KB Output is correct
7 Correct 83 ms 63172 KB Output is correct
8 Correct 83 ms 63268 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 63216 KB Output is correct
2 Correct 85 ms 63276 KB Output is correct
3 Correct 90 ms 63264 KB Output is correct
4 Correct 84 ms 63332 KB Output is correct
5 Correct 89 ms 63300 KB Output is correct
6 Correct 85 ms 63252 KB Output is correct
7 Correct 85 ms 63288 KB Output is correct
8 Correct 86 ms 63308 KB Output is correct
9 Correct 85 ms 63356 KB Output is correct
10 Correct 86 ms 63264 KB Output is correct
11 Correct 83 ms 63244 KB Output is correct
12 Correct 83 ms 63216 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 63192 KB Output is correct
2 Correct 87 ms 63604 KB Output is correct
3 Correct 86 ms 64436 KB Output is correct
4 Correct 94 ms 69444 KB Output is correct
5 Correct 94 ms 68556 KB Output is correct
6 Correct 107 ms 67720 KB Output is correct
7 Correct 85 ms 64248 KB Output is correct
8 Correct 85 ms 63304 KB Output is correct
9 Correct 96 ms 63856 KB Output is correct
10 Correct 180 ms 96396 KB Output is correct
11 Correct 146 ms 85580 KB Output is correct
12 Correct 101 ms 63940 KB Output is correct
13 Correct 86 ms 64752 KB Output is correct
14 Correct 84 ms 63296 KB Output is correct
15 Correct 188 ms 96912 KB Output is correct
16 Correct 153 ms 88020 KB Output is correct
17 Correct 98 ms 67216 KB Output is correct
18 Correct 202 ms 95732 KB Output is correct