oj.uz

Submission #1054063

# Submission time Handle Problem Language Result Execution time Memory
1054063 2024-08-12T05:37:27 Z juicy 마스코트 (JOI13_mascots) C++17
100 / 100
 110 ms 106728 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 3e3 + 5, MD = 1e9 + 7;

int add(int a, int b) {
  if ((a += b) >= MD) {
    a -= MD;
  }
  return a;
}

int fact[N * N], dp[N][N], C[N][N];

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  int r, c, n; cin >> r >> c >> n;
  fact[0] = 1;
  for (int i = 1; i <= r * c; ++i) {
    fact[i] = (long long) fact[i - 1] * i % MD;
  }
  for (int i = 0; i <= max(r, c); ++i) {
    C[i][0] = C[i][i] = 1;
    for (int j = 1; j < i; ++j) {
      C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]);
    }
  }
  array<int, 2> mi{r, c}, ma{};
  for (int _ = 0; _ < n; ++_) {
    for (int i = 0; i < 2; ++i) {
      int x; cin >> x;
      mi[i] = min(mi[i], x);
      ma[i] = max(ma[i], x); 
    }
  }
  int a = ma[0] - mi[0] + 1, b = ma[1] - mi[1] + 1;
  dp[a][b] = fact[a * b - n];
  for (int i = a; i <= r; ++i) {
    for (int j = b; j <= c; ++j) {
      dp[i][j] = add(dp[i][j], (long long) dp[i - 1][j] * fact[j] % MD);
      dp[i][j] = add(dp[i][j], (long long) dp[i][j - 1] * fact[i] % MD);
    }
  }
  auto res = (long long) dp[r][c] * C[r - a][mi[0] - 1] % MD * C[c - b][mi[1] - 1] % MD;
  cout << res;
  return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 2 ms 8668 KB Output is correct
3 Correct 3 ms 9404 KB Output is correct
4 Correct 12 ms 24156 KB Output is correct
5 Correct 12 ms 23900 KB Output is correct
6 Correct 17 ms 24924 KB Output is correct
7 Correct 11 ms 29276 KB Output is correct
8 Correct 21 ms 43604 KB Output is correct
9 Correct 50 ms 73716 KB Output is correct
10 Correct 98 ms 99412 KB Output is correct
11 Correct 83 ms 91740 KB Output is correct
12 Correct 46 ms 70864 KB Output is correct
13 Correct 5 ms 17500 KB Output is correct
14 Correct 47 ms 73300 KB Output is correct
15 Correct 110 ms 106728 KB Output is correct
16 Correct 87 ms 83796 KB Output is correct
17 Correct 60 ms 78604 KB Output is correct
18 Correct 109 ms 105040 KB Output is correct