oj.uz

Submission #56989

# Submission time Handle Problem Language Result Execution time Memory
56989 2018-07-13T12:27:53 Z choikiwon 마스코트 (JOI13_mascots) C++17
40 / 100
 104 ms 74448 KB 
#include<bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
const int MN = 100010;
const int MX = 3010;

int exp(int x, int n) {
    int ret = 1;
    while(n) {
        if(n & 1) ret = 1LL * ret * x % mod;
        x = 1LL * x * x % mod;
        n >>= 1;
    }
    return ret;
}
int inv(int x) {
    return exp(x, mod - 2);
}
int fact[MN], invf[MN];
int comb(int n, int k) {
    if(n < k) return 0;
    return 1LL * fact[n] * invf[k] % mod * invf[n - k] % mod;
}

int R, C, N;
int mn1, mn2, mx1, mx2;

int cc[MX][MX];
int dp(int r, int c) {
    int &ret = cc[r][c];
    if(ret != -1) return ret;
    if(r == R && c == C) return ret = 1;

    ret = 0;
    if(r < R) {
        ret += 1LL * dp(r + 1, c) * fact[c] % mod;
        ret %= mod;
    }
    if(c < C) {
        ret += 1LL * dp(r, c + 1) * fact[r] % mod;
        ret %= mod;
    }
    return ret;
}

int main() {
    fact[0] = 1;
    for(int i = 1; i < MN; i++) {
        fact[i] = 1LL * fact[i - 1] * i % mod;
    }
    for(int i = 0; i < MN; i++) {
        invf[i] = inv(fact[i]);
    }

    scanf("%d %d %d", &R, &C, &N);

    mn1 = mn2 = 1e9;
    mx1 = mx2 = -1e9;
    for(int i = 0; i < N; i++) {
        int r, c; scanf("%d %d", &r, &c);
        mn1 = min(mn1, r);
        mx1 = max(mx1, r);
        mn2 = min(mn2, c);
        mx2 = max(mx2, c);
    }

    int r = mx1 - mn1 + 1;
    int c = mx2 - mn2 + 1;

    memset(cc, -1, sizeof(cc));
    int ans = 1LL * fact[r * c - N] * dp(r, c) % mod;
    ans = 1LL * ans * comb(R - r, mn1 - 1) % mod;
    ans = 1LL * ans * comb(C - c, mn2 - 1) % mod;
    printf("%d", ans);
}

Compilation message

mascots.cpp: In function 'int main()':
mascots.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &R, &C, &N);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mascots.cpp:61:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int r, c; scanf("%d %d", &r, &c);
                   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 36600 KB Output is correct
2 Correct 59 ms 36752 KB Output is correct
3 Correct 52 ms 36776 KB Output is correct
4 Correct 49 ms 36824 KB Output is correct
5 Correct 53 ms 36824 KB Output is correct
6 Correct 50 ms 36824 KB Output is correct
7 Correct 54 ms 36824 KB Output is correct
8 Correct 53 ms 36824 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 37064 KB Output is correct
2 Correct 53 ms 37064 KB Output is correct
3 Correct 49 ms 37064 KB Output is correct
4 Correct 50 ms 37188 KB Output is correct
5 Correct 52 ms 37188 KB Output is correct
6 Correct 51 ms 37188 KB Output is correct
7 Correct 52 ms 37188 KB Output is correct
8 Correct 52 ms 37188 KB Output is correct
9 Correct 52 ms 37188 KB Output is correct
10 Correct 51 ms 37188 KB Output is correct
11 Correct 51 ms 37188 KB Output is correct
12 Correct 52 ms 37188 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 37252 KB Output is correct
2 Correct 53 ms 37256 KB Output is correct
3 Correct 53 ms 37288 KB Output is correct
4 Correct 75 ms 37336 KB Output is correct
5 Correct 76 ms 37336 KB Output is correct
6 Correct 86 ms 38100 KB Output is correct
7 Runtime error 104 ms 74448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -