oj.uz

Submission #374729

# Submission time Handle Problem Language Result Execution time Memory
374729 2021-03-08T03:31:43 Z phathnv 마스코트 (JOI13_mascots) C++11
100 / 100
 217 ms 99820 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 = 1; i <= r; i++)
        for(int j = 1; 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 93 ms 63468 KB Output is correct
2 Correct 91 ms 63468 KB Output is correct
3 Correct 92 ms 63468 KB Output is correct
4 Correct 91 ms 63596 KB Output is correct
5 Correct 92 ms 63468 KB Output is correct
6 Correct 90 ms 63468 KB Output is correct
7 Correct 91 ms 63468 KB Output is correct
8 Correct 91 ms 63468 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 63468 KB Output is correct
2 Correct 92 ms 63468 KB Output is correct
3 Correct 95 ms 63468 KB Output is correct
4 Correct 92 ms 63468 KB Output is correct
5 Correct 91 ms 63468 KB Output is correct
6 Correct 92 ms 63596 KB Output is correct
7 Correct 103 ms 63596 KB Output is correct
8 Correct 92 ms 63604 KB Output is correct
9 Correct 95 ms 63724 KB Output is correct
10 Correct 91 ms 63468 KB Output is correct
11 Correct 92 ms 63596 KB Output is correct
12 Correct 90 ms 63468 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 64492 KB Output is correct
2 Correct 94 ms 64856 KB Output is correct
3 Correct 98 ms 65004 KB Output is correct
4 Correct 103 ms 69996 KB Output is correct
5 Correct 104 ms 69868 KB Output is correct
6 Correct 121 ms 72172 KB Output is correct
7 Correct 116 ms 75116 KB Output is correct
8 Correct 145 ms 87020 KB Output is correct
9 Correct 213 ms 99356 KB Output is correct
10 Correct 186 ms 96620 KB Output is correct
11 Correct 184 ms 93164 KB Output is correct
12 Correct 205 ms 99436 KB Output is correct
13 Correct 104 ms 69228 KB Output is correct
14 Correct 214 ms 98796 KB Output is correct
15 Correct 216 ms 99692 KB Output is correct
16 Correct 165 ms 89068 KB Output is correct
17 Correct 212 ms 99180 KB Output is correct
18 Correct 217 ms 99820 KB Output is correct