oj.uz

Submission #448229

# Submission time Handle Problem Language Result Execution time Memory
448229 2021-07-29T10:47:02 Z hizuna 마스코트 (JOI13_mascots) C++17
100 / 100
 375 ms 207308 KB 
#include <bits/stdc++.h>

using namespace std;
using lint = long long;

const lint mod = 1e9 + 7;

int R, C, N;
lint f[3007][3007], fact[9000003], inv_fact[9000003], res;

lint modexp(lint a, lint b) {
    lint ans = 1;
    while(b > 0) {
        if(b % 2) ans = ans * a % mod;
        a = a * a % mod, b /= 2;
    }
    return ans;
}

lint F(int x, int y) {
    if(x > R || y > C) return 0;
    if(x == R && y == C) return 1;
    if(f[x][y]) return f[x][y];

    lint fw = F(x + 1, y) * fact[y] % mod;
    lint fh = F(x, y + 1) * fact[x] % mod;
    return f[x][y]= (fw + fh) % mod;
}

void set_fact(int n) {
    fact[0] = 1;
    for(int i = 1; i <= n; i++)
        fact[i] = fact[i - 1] * i % mod;

    inv_fact[n] = modexp(fact[n], mod - 2);
    for(int i = n; i >= 1; i--)
        inv_fact[i - 1] = inv_fact[i] * i % mod;
}

lint nCr(int n, int r) {
    if(r > n) return 0;
    return fact[n] * inv_fact[n - r] % mod * inv_fact[r] % mod;
}

int main() {
    scanf("%d%d%d", &R, &C, &N);
    set_fact(R * C);
    int x1 = R + 1, y1 = C + 1, x2 = 0, y2 = 0;
    
    for(int i = 0; i < N; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        x1 = min(x1, x), y1 = min(y1, y);
        x2 = max(x2, x), y2 = max(y2, y);
    }

    res = F(x2 - x1 + 1, y2 - y1 + 1) % mod;
    res = res * fact[(x2 - x1 + 1) * (y2 - y1 + 1) - N] % mod;
    res = res * nCr(R - (x2 - x1 + 1), x1 - 1) % mod;
    res = res * nCr(C - (y2 - y1 + 1), y1 - 1) % mod;
    
    printf("%lld\n", res);
    
    return 0;
}

Compilation message

mascots.cpp: In function 'int main()':
mascots.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     scanf("%d%d%d", &R, &C, &N);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
mascots.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         scanf("%d%d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 972 KB Output is correct
2 Correct 3 ms 2036 KB Output is correct
3 Correct 5 ms 3148 KB Output is correct
4 Correct 36 ms 21940 KB Output is correct
5 Correct 37 ms 21040 KB Output is correct
6 Correct 53 ms 21120 KB Output is correct
7 Correct 33 ms 28908 KB Output is correct
8 Correct 68 ms 62944 KB Output is correct
9 Correct 159 ms 141220 KB Output is correct
10 Correct 350 ms 185028 KB Output is correct
11 Correct 256 ms 162248 KB Output is correct
12 Correct 147 ms 124868 KB Output is correct
13 Correct 15 ms 12456 KB Output is correct
14 Correct 154 ms 141148 KB Output is correct
15 Correct 375 ms 207308 KB Output is correct
16 Correct 273 ms 145032 KB Output is correct
17 Correct 165 ms 145636 KB Output is correct
18 Correct 367 ms 204512 KB Output is correct