oj.uz

Submission #535785

# Submission time Handle Problem Language Result Execution time Memory
535785 2022-03-11T07:45:31 Z Soumya1 Tents (JOI18_tents) C++17
100 / 100
 136 ms 35676 KB 
#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
using namespace std;
template<const int mod, const int modPhi>
struct Mint {
  int v;
  Mint() { v = 0; }
  Mint(int x) { v = x % mod; if (v < 0) v += mod; }
  Mint(long long x) { v = x % mod; if (v < 0) v += mod; }
  friend bool operator==(const Mint &a, const Mint &b) { return a.v == b.v; }
  friend bool operator!=(const Mint &a, const Mint &b) { return a.v != b.v; }
  friend bool operator<(const Mint &a, const Mint &b) { return a.v < b.v; }
  friend bool operator<=(const Mint &a, const Mint &b) { return a.v <= b.v; }
  friend bool operator>(const Mint &a, const Mint &b) { return a.v > b.v; }
  friend bool operator>=(const Mint &a, const Mint &b) { return a.v >= b.v; }
  Mint& operator+=(const Mint &a) { v += a.v; if (v >= mod) v -= mod; return *this; }
  Mint& operator-=(const Mint &a) { v -= a.v; if (v < 0) v += mod; return *this; }
  Mint& operator*=(const Mint &a) { v = (1LL * v * a.v) % mod; return *this; }
  Mint operator-() { return Mint(-v); }
  Mint& operator++() { return *this += 1; }
  Mint& operator--() { return *this -= 1; }
  friend Mint operator+(Mint a, const Mint b) { return a += b; }
  friend Mint operator-(Mint a, const Mint b) { return a -= b; }
  friend Mint operator*(Mint a, const Mint b) { return a *= b; }
  friend Mint min(Mint a, Mint b) { return (a < b ? b : a); }
  friend Mint max(Mint a, Mint b) { return (a > b ? a : b); }
  friend Mint power(Mint a, long long b) {
    Mint res = 1;
    while (b > 0) {
      if (b & 1) {
        res *= a;
      }
      a *= a, b >>= 1;
    }
    return res;
  }
  friend Mint inv(const Mint &a) { return power(a, modPhi - 1); }
  Mint operator/=(const Mint &a) { *this *= inv(a); return *this; }
  friend Mint operator/(Mint a, const Mint b) { return a /= b; }
  friend istream& operator>>(istream &in, Mint &a) { return in >> a.v; }
  friend ostream& operator<<(ostream &out, Mint a) { return out << a.v; }
};
const int mod = 1e9 + 7;
using mint = Mint<mod, mod - 1>;
void testCase() {
  int w, h;
  cin >> w >> h;
  vector<vector<mint>> dp(w + 1, vector<mint> (h + 1, mint(1)));
  for (int i = 1; i <= w; i++) {
    for (int j = 1; j <= h; j++) {
      dp[i][j] = mint(4 * j) * dp[i - 1][j - 1];
      dp[i][j] += dp[i - 1][j];
      if (j >= 2) dp[i][j] += mint(j * (j - 1) / 2) * dp[i - 1][j - 2];
      if (i >= 2) dp[i][j] += mint((i - 1) * j) * dp[i - 2][j - 1];
    }
  }
  cout << dp[w][h] - 1 << endl;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  testCase();
  return 0;
}

Subtask #1
48.0 / 48.0

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

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 448 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 2 ms 688 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 87 ms 22328 KB Output is correct
16 Correct 6 ms 1728 KB Output is correct
17 Correct 20 ms 5204 KB Output is correct
18 Correct 24 ms 6356 KB Output is correct
19 Correct 100 ms 25952 KB Output is correct
20 Correct 79 ms 20692 KB Output is correct
21 Correct 55 ms 13780 KB Output is correct
22 Correct 50 ms 13640 KB Output is correct
23 Correct 29 ms 7776 KB Output is correct
24 Correct 136 ms 35676 KB Output is correct
25 Correct 130 ms 26572 KB Output is correct
26 Correct 118 ms 30408 KB Output is correct
27 Correct 124 ms 34304 KB Output is correct