oj.uz

Submission #37469

# Submission time Handle Problem Language Result Execution time Memory
37469 2017-12-25T16:02:31 Z nickyrio 마스코트 (JOI13_mascots) C++14
100 / 100
 356 ms 186660 KB 
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i<=b ; i++)
#define FORD(i, a, b) for (int i = a; i>=b; i--)
#define REP(i, a) for (int i = 0; i<a; i++)
#define N 3333
#define pp pair<int, int>
#define IO cin.tie(NULL);cout.tie(NULL);
#define bit(S, i) (((S) >> i) & 1)
template<typename T> inline void read(T &x) {
    char c;
    bool neg = false;
    while (!isdigit(c = getchar()) && c != '-');
    x = 0;
    if (c == '-') {
        neg = true;
        c = getchar();
    }
    do {
        x = x * 10 + c - '0';
    } while (isdigit(c = getchar()));
    if (neg) x = -x;
}
template<typename T> inline void write(T x) {
    if (x < 0) {
        putchar('-');
        write(-x);return;
    }
    if (x < 10) {
        putchar(char(x + 48));
    }
    else {
        write(x/10);
        putchar(char(48 + x%10));
    }
}
template<typename T> inline void writeln(T x) {
    write(x);
    putchar('\n');
}
using namespace std;

int q, n, m, a[N][N];
const int MOD = 1e9 + 7;
int gt[N * N], dp[N][N], c[N][N];
bool used[N][N];

int cal(int r, int c) {
    if (r == m && c == n) return 1;
    if (used[r][c]) return dp[r][c];
    used[r][c] = true;
    dp[r][c] = 0;
    if (r != m) {
        dp[r][c] = (dp[r][c] + 1ll * cal(r + 1, c) * gt[c] % MOD) % MOD;
    }
    if (c != n) {
        dp[r][c] = (dp[r][c] + 1ll * cal(r, c + 1) * gt[r] % MOD) % MOD;
    }
    return dp[r][c];
}

void init() {
    FOR(i, 0, max(m, n)) c[0][i] = 1;
    FOR(i, 1, max(m, n)) {
        c[i][i] = 1;
        FOR(j, i + 1, max(m, n)) {
            c[i][j] = (c[i][j - 1] + c[i - 1][j - 1]) % MOD;
        }
    }
}
int main() {
    IO;
    //freopen("LANDS.inp","r",stdin);
    //freopen("LANDS.out","w",stdout);
    read(m);read(n);
    gt[0] = 1;
    FOR(i, 1, m * n) gt[i] = 1ll * gt[i - 1] * i % MOD;
    read(q);
    int mnx = 1e9, mny = 1e9, mxx = -1e9, mxy = -1e9;
    int u, v;
    while (q--) {
        read(u);read(v);
        a[u][v] = 1;
        mnx = min(u, mnx);
        mxx = max(u, mxx);
        mny = min(v, mny);
        mxy = max(v, mxy);
    }
    if (n == 0) {
        writeln(gt[n * m]);
        return 0;
    }
    init();
    int total = cal(mxx - mnx + 1, mxy - mny + 1);
    FOR(i, 1, m) FOR(j, 1, n) a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
    int cnt = a[mxx][mxy] - a[mxx][mny - 1] - a[mnx - 1][mxy] + a[mnx - 1][mny - 1];
    total = 1ll * total * gt[(mxx - mnx + 1) * (mxy - mny + 1) - cnt] % MOD;
    total = (1ll * total * c[mnx - 1][m - (mxx - mnx + 1)]) % MOD;
    total = (1ll * total * c[mny - 1][n - (mxy - mny + 1)]) % MOD;
    writeln(total);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 186440 KB Output is correct
2 Correct 3 ms 186440 KB Output is correct
3 Correct 6 ms 186440 KB Output is correct
4 Correct 36 ms 186440 KB Output is correct
5 Correct 29 ms 186440 KB Output is correct
6 Correct 36 ms 186440 KB Output is correct
7 Correct 29 ms 186440 KB Output is correct
8 Correct 53 ms 186440 KB Output is correct
9 Correct 143 ms 186440 KB Output is correct
10 Correct 269 ms 186660 KB Output is correct
11 Correct 229 ms 186588 KB Output is correct
12 Correct 139 ms 186440 KB Output is correct
13 Correct 13 ms 186440 KB Output is correct
14 Correct 159 ms 186440 KB Output is correct
15 Correct 356 ms 186648 KB Output is correct
16 Correct 229 ms 186616 KB Output is correct
17 Correct 143 ms 186440 KB Output is correct
18 Correct 326 ms 186648 KB Output is correct