oj.uz

Submission #35019

# Submission time Handle Problem Language Result Execution time Memory
35019 2017-11-17T10:00:40 Z ztrong 마스코트 (JOI13_mascots) C++14
100 / 100
 173 ms 213816 KB 
#include <bits/stdc++.h>
using namespace std;

#define llint long long

void openFile() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    #ifdef Tr___
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
    #else
    //freopen("name.inp", "r", stdin);
    //freopen("name.out", "w", stdout);
    #endif
}

const int maxN = 3e3 + 5;
const int maxM = 1e6 + 5;
const llint INF = 1e9 + 7;

int N, R, C;
int xmin = INF, xmax = -INF, ymin = INF, ymax = -INF;
llint dp[maxN][maxN], gt[maxN * maxN], cc[maxN][maxN];

void enter() {
    cin >> R >> C;
    cin >> N;
    for (int i = 1; i <= N; ++i) {
        int x, y;
        cin >> x >> y;
        xmin = min(xmin, x);
        xmax = max(xmax, x);
        ymin = min(ymin, y);
        ymax = max(ymax, y);
    }
}

llint pw(int x, int n) {
    if (n == 0) return 1;
    if (n == 1) return x % INF;
    llint res = pw(x, n / 2);
    res = res * res % INF;
    if (n & 1) res = res * x % INF;
    return res;
}

inline llint getC(int x, int n) {
    if (x == 0) return 1;
    if (x == n) return 1;
    //n! / (x! * (n - x)!)

    return gt[n] * pw(gt[x], (INF - 2)) % INF * pw(gt[n - x], (INF - 2)) % INF;
}

void solve() {
    gt[0] = 1;
    for (int i = 1; i <= R * C; ++i) {
        gt[i] = gt[i - 1] * i % INF;
    }
    int r = xmax - xmin + 1, c = ymax - ymin + 1;
    dp[r][c] = gt[r * c - N];
    for (int i = r; i <= R; ++i) {
        for (int j = c; j <= C; ++j) {
            //cout << i << " " << j << endl;
            dp[i + 1][j] = (dp[i + 1][j] + dp[i][j] * gt[j]) % INF;
            dp[i][j + 1] = (dp[i][j + 1] + dp[i][j] * gt[i]) % INF;
        }
    }

    llint res = dp[R][C];
    //cout << res << endl;
    res = res * getC(xmin - 1, R - xmax + xmin - 1) % INF;
    //cout << res << endl;
    res = res * getC(ymin - 1, C - ymax + ymin - 1) % INF;
    cout << res << endl;
}

int main() {
    openFile();
    enter();
    solve();
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 213816 KB Output is correct
2 Correct 0 ms 213816 KB Output is correct
3 Correct 0 ms 213816 KB Output is correct
4 Correct 0 ms 213816 KB Output is correct
5 Correct 0 ms 213816 KB Output is correct
6 Correct 0 ms 213816 KB Output is correct
7 Correct 0 ms 213816 KB Output is correct
8 Correct 0 ms 213816 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 213816 KB Output is correct
2 Correct 0 ms 213816 KB Output is correct
3 Correct 0 ms 213816 KB Output is correct
4 Correct 0 ms 213816 KB Output is correct
5 Correct 0 ms 213816 KB Output is correct
6 Correct 0 ms 213816 KB Output is correct
7 Correct 0 ms 213816 KB Output is correct
8 Correct 0 ms 213816 KB Output is correct
9 Correct 0 ms 213816 KB Output is correct
10 Correct 0 ms 213816 KB Output is correct
11 Correct 0 ms 213816 KB Output is correct
12 Correct 0 ms 213816 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 213816 KB Output is correct
2 Correct 0 ms 213816 KB Output is correct
3 Correct 0 ms 213816 KB Output is correct
4 Correct 6 ms 213816 KB Output is correct
5 Correct 16 ms 213816 KB Output is correct
6 Correct 33 ms 213816 KB Output is correct
7 Correct 9 ms 213816 KB Output is correct
8 Correct 19 ms 213816 KB Output is correct
9 Correct 83 ms 213816 KB Output is correct
10 Correct 119 ms 213816 KB Output is correct
11 Correct 79 ms 213816 KB Output is correct
12 Correct 53 ms 213816 KB Output is correct
13 Correct 6 ms 213816 KB Output is correct
14 Correct 63 ms 213816 KB Output is correct
15 Correct 136 ms 213816 KB Output is correct
16 Correct 113 ms 213816 KB Output is correct
17 Correct 79 ms 213816 KB Output is correct
18 Correct 173 ms 213816 KB Output is correct