Submission #417061

#	Time	Username	Problem	Language	Result	Execution time	Memory
417061		proteam23	마스코트 (JOI13_mascots)	C++14	100 / 100	202 ms	96912 KiB

mascots

#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 / 10
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60