oj.uz

Submission #1023871

# Submission time Handle Problem Language Result Execution time Memory
1023871 2024-07-15T08:17:34 Z MilosMilutinovic 마스코트 (JOI13_mascots) C++14
100 / 100
 210 ms 107356 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 3003 * 3003;
const int md = 1e9 + 7;

int f[N], inv[N];

int add(int x, int y) {
  return x + y < md ? x + y : x + y - md;
}

void sadd(int& x, int y) {
  x = add(x, y);
}

int mul(int x, int y) {
  return x * 1LL * y % md;
}

void smul(int& x, int y) {
  x = mul(x, y);
}

int ckpow(int x, int k) {
  int ret = 1;
  while (k) {
    if (k & 1) {
      ret = mul(ret, x);
    }
    x = mul(x, x);
    k >>= 1;
  }
  return ret;
}

int C(int n, int k) {
  if (n < 0 || k < 0 || n < k) {
    return 0;
  }
  return mul(f[n], mul(inv[k], inv[n - k]));
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  f[0] = 1;
  for (int i = 1; i < N; i++) {
    f[i] = mul(f[i - 1], i);
  }
  inv[N - 1] = ckpow(f[N - 1], md - 2);
  for (int i = N - 2; i >= 0; i--) {
    inv[i] = mul(inv[i + 1], i + 1);
  }
  int r, c;
  cin >> r >> c;
  int n;
  cin >> n;
  int lx = r, rx = -1, ly = c, ry = -1;
  for (int i = 0; i < n; i++) {
    int x, y;
    cin >> x >> y;
    lx = min(lx, x);
    rx = max(rx, x);
    ly = min(ly, y);
    ry = max(ry, y);
  }
  int len_x = rx - lx + 1;
  int len_y = ry - ly + 1;
  int total = len_x * len_y - n;
  vector<vector<int>> dp(r + 1, vector<int>(c + 1));
  dp[len_x][len_y] = f[total];
  for (int x = 1; x <= r; x++) {
    for (int y = 1; y <= c; y++) {
      if (x < r) {
        sadd(dp[x + 1][y], mul(dp[x][y], f[y]));
      }
      if (y < c) {
        sadd(dp[x][y + 1], mul(dp[x][y], f[x]));
      }
    }
  }
  int res = dp[r][c];
  smul(res, C(r - len_x, lx - 1));
  smul(res, C(c - len_y, ly - 1));
  cout << res << '\n';
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 70996 KB Output is correct
2 Correct 119 ms 70996 KB Output is correct
3 Correct 118 ms 70984 KB Output is correct
4 Correct 124 ms 70984 KB Output is correct
5 Correct 124 ms 70792 KB Output is correct
6 Correct 121 ms 70776 KB Output is correct
7 Correct 120 ms 70996 KB Output is correct
8 Correct 120 ms 70876 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 70816 KB Output is correct
2 Correct 122 ms 70800 KB Output is correct
3 Correct 121 ms 70988 KB Output is correct
4 Correct 120 ms 70996 KB Output is correct
5 Correct 127 ms 70992 KB Output is correct
6 Correct 121 ms 70892 KB Output is correct
7 Correct 122 ms 70996 KB Output is correct
8 Correct 122 ms 70996 KB Output is correct
9 Correct 124 ms 71024 KB Output is correct
10 Correct 130 ms 70920 KB Output is correct
11 Correct 123 ms 70948 KB Output is correct
12 Correct 121 ms 70976 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 71028 KB Output is correct
2 Correct 121 ms 71252 KB Output is correct
3 Correct 124 ms 71244 KB Output is correct
4 Correct 127 ms 74324 KB Output is correct
5 Correct 128 ms 74256 KB Output is correct
6 Correct 134 ms 75600 KB Output is correct
7 Correct 133 ms 77652 KB Output is correct
8 Correct 155 ms 86556 KB Output is correct
9 Correct 210 ms 106808 KB Output is correct
10 Correct 188 ms 100436 KB Output is correct
11 Correct 191 ms 100436 KB Output is correct
12 Correct 191 ms 102996 KB Output is correct
13 Correct 126 ms 73556 KB Output is correct
14 Correct 200 ms 106284 KB Output is correct
15 Correct 206 ms 107012 KB Output is correct
16 Correct 173 ms 94692 KB Output is correct
17 Correct 203 ms 106836 KB Output is correct
18 Correct 206 ms 107356 KB Output is correct