oj.uz

Submission #37224

# Submission time Handle Problem Language Result Execution time Memory
37224 2017-12-22T16:58:13 Z nickyrio 마스코트 (JOI13_mascots) C++14
100 / 100
 356 ms 151944 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 3003
#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];

long long 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] + cal(r + 1, c) * gt[c] % MOD) % MOD;
    }
    if (c != n) {
        dp[r][c] = (dp[r][c] + 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();
    long long 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 151728 KB Output is correct
2 Correct 0 ms 151728 KB Output is correct
3 Correct 0 ms 151728 KB Output is correct
4 Correct 0 ms 151728 KB Output is correct
5 Correct 0 ms 151728 KB Output is correct
6 Correct 0 ms 151728 KB Output is correct
7 Correct 0 ms 151728 KB Output is correct
8 Correct 0 ms 151728 KB Output is correct

Subtask #2
30.0 / 30.0

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

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 151728 KB Output is correct
2 Correct 3 ms 151728 KB Output is correct
3 Correct 0 ms 151728 KB Output is correct
4 Correct 29 ms 151728 KB Output is correct
5 Correct 36 ms 151728 KB Output is correct
6 Correct 49 ms 151728 KB Output is correct
7 Correct 26 ms 151728 KB Output is correct
8 Correct 69 ms 151728 KB Output is correct
9 Correct 143 ms 151728 KB Output is correct
10 Correct 286 ms 151944 KB Output is correct
11 Correct 226 ms 151876 KB Output is correct
12 Correct 176 ms 151728 KB Output is correct
13 Correct 13 ms 151728 KB Output is correct
14 Correct 133 ms 151728 KB Output is correct
15 Correct 339 ms 151940 KB Output is correct
16 Correct 243 ms 151900 KB Output is correct
17 Correct 156 ms 151728 KB Output is correct
18 Correct 356 ms 151940 KB Output is correct