oj.uz

Submission #892711

# Submission time Handle Problem Language Result Execution time Memory
892711 2023-12-25T17:49:27 Z box Tents (JOI18_tents) C++17
100 / 100
 124 ms 89104 KB 
#include <bits/stdc++.h>
using namespace std;

#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;

const int N = 3000;
const i64 MOD = 1e9 + 7;

int h, w;
int take[N + 1][N + 1];
i64 roll[N + 1];
i64 fac[N + 1], ifac[N + 1], p4[N + 1];
i64 dp[N + 1][N + 1];

i64 inv(i64 a) {
    return a == 1 ? 1 : inv(MOD % a) * (MOD - MOD / a) % MOD;
}

i64 nck(int n, int k) {
    if (n < k || k < 0) return 0;
    return fac[n] * ifac[k] % MOD * ifac[n - k] % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    roll[1] = 1;
    for (int i = 3; i <= N; i += 2) roll[i] = roll[i - 2] * i % MOD;
    fac[0] = ifac[0] = 1;
    for (int i = 1; i <= N; i++) fac[i] = fac[i - 1] * i % MOD, ifac[i] = inv(fac[i]);
    p4[0] = 1;
    for (int i = 1; i <= N; i++) p4[i] = p4[i - 1] * 4 % MOD;
    for (int k = 0; k <= N / 2; k++) for (int n = 0; n <= N; n++)
        take[k][n] = nck(n, k * 2) * (!k ? 1 : roll[k * 2 - 1]) % MOD;
    for (int i = 0; i <= N; i++) dp[i][0] = dp[0][i] = 1;
    for (int n = 1; n <= N; n++) for (int m = 1; m <= N; m++) {
        // fix what to do on the last row
        dp[n][m] += dp[n - 1][m]; // do nothing
        dp[n][m] += dp[n - 1][m - 1] * m * 4 % MOD; // single cell
        if (m >= 2) dp[n][m] += dp[n - 1][m - 2] * nck(m, 2) % MOD; // paired up, horizontal
        if (n >= 2) dp[n][m] += dp[n - 2][m - 1] * m * (n - 1) % MOD; // paired up, vertical
        dp[n][m] %= MOD;
    }
    cin >> h >> w;
    cout << dp[h][w] - 1 << '\n';
}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 88848 KB Output is correct
2 Correct 116 ms 88840 KB Output is correct
3 Correct 110 ms 88852 KB Output is correct
4 Correct 116 ms 88856 KB Output is correct
5 Correct 118 ms 88668 KB Output is correct
6 Correct 118 ms 88660 KB Output is correct
7 Correct 112 ms 88656 KB Output is correct
8 Correct 114 ms 88852 KB Output is correct
9 Correct 122 ms 88656 KB Output is correct
10 Correct 113 ms 88668 KB Output is correct
11 Correct 111 ms 89104 KB Output is correct
12 Correct 112 ms 88780 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 88848 KB Output is correct
2 Correct 116 ms 88840 KB Output is correct
3 Correct 110 ms 88852 KB Output is correct
4 Correct 116 ms 88856 KB Output is correct
5 Correct 118 ms 88668 KB Output is correct
6 Correct 118 ms 88660 KB Output is correct
7 Correct 112 ms 88656 KB Output is correct
8 Correct 114 ms 88852 KB Output is correct
9 Correct 122 ms 88656 KB Output is correct
10 Correct 113 ms 88668 KB Output is correct
11 Correct 111 ms 89104 KB Output is correct
12 Correct 112 ms 88780 KB Output is correct
13 Correct 112 ms 88848 KB Output is correct
14 Correct 113 ms 88852 KB Output is correct
15 Correct 111 ms 88656 KB Output is correct
16 Correct 121 ms 88852 KB Output is correct
17 Correct 114 ms 88852 KB Output is correct
18 Correct 112 ms 88784 KB Output is correct
19 Correct 112 ms 88788 KB Output is correct
20 Correct 111 ms 88848 KB Output is correct
21 Correct 116 ms 88660 KB Output is correct
22 Correct 110 ms 88852 KB Output is correct
23 Correct 110 ms 88852 KB Output is correct
24 Correct 112 ms 88656 KB Output is correct
25 Correct 112 ms 88856 KB Output is correct
26 Correct 112 ms 88660 KB Output is correct
27 Correct 112 ms 88852 KB Output is correct