oj.uz

Submission #364644

# Submission time Handle Problem Language Result Execution time Memory
364644 2021-02-09T16:21:23 Z parsabahrami Tents (JOI18_tents) C++17
100 / 100
 252 ms 63340 KB 
// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

int Pow(int a, int b, int md, int ret = 1) {
    for (; b; b >>= 1, a = 1ll * a * a % md) {
        if (b & 1) ret = 1ll * ret * a % md;
    }
    return ret;
}

const int N = 3e3 + 10, MOD = 1e9 + 7;
int dp[N][N], pd[N][N], F[N], I[N], w, h;

int C(int x, int y) {
    if (y < 0 || x < y) return 0;
    return 1ll * F[x] * I[y] % MOD * I[x - y] % MOD;
}

int main() {
    scanf("%d%d", &w, &h);
    F[0] = 1;
    for (int i = 1; i < N; i++) F[i] = 1ll * F[i - 1] * i % MOD;
    I[N - 1] = Pow(F[N - 1], MOD - 2, MOD);
    for (int i = N - 1; i; i--) {
        I[i - 1] = I[i] * 1ll * i % MOD;
    }
    pd[0][0] = 1;
    for (int i = 0; i < max(w, h); i++) {
        for (int j = 0; j <= i; j++) {
            pd[i + 1][j + 1] = (pd[i + 1][j + 1] + pd[i][j]) % MOD;
            if (j) pd[i + 1][j - 1] = (pd[i + 1][j - 1] + pd[i][j] * 1ll * j % MOD) % MOD;
        }
    }
    for (int i = 0; i <= max(w, h); i++) {
        for (int j = 0; j <= max(w, h); j++) {
            if (!i || !j) dp[i][j] = 1;
            else dp[i][j] = (dp[i - 1][j] + 1ll * dp[i - 1][j - 1] * 4 * j % MOD) % MOD;
        }
    }
    int ret = 0;
    for (int c1 = 0; c1 <= max(w, h); c1++) {
        for (int c2 = 0; c2 <= max(w, h); c2++) {
            if (w - 2 * c1 - c2 >= 0 && h - 2 * c2 - c1 >= 0) {
                int x = C(w, 2 * c1) * 1ll * C(w - 2 * c1, c2) % MOD;
                x = 1ll * x * pd[2 * c1][0] % MOD;
                int y = C(h, 2 * c2) * 1ll * C(h - 2 * c2, c1) % MOD;
                y = 1ll * y * pd[2 * c2][0] % MOD;
                int nw = 1ll * x * y % MOD * F[c1] % MOD * F[c2] % MOD * dp[w - 2 * c1 - c2][h - 2 * c2 - c1] % MOD;
                ret = (ret + nw) % MOD;
            }
        }
    }
    printf("%d\n", ret - 1);
    return 0;
}

Compilation message

tents.cpp: In function 'int main()':
tents.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   29 |     scanf("%d%d", &w, &h);
      |     ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 2 ms 2028 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 2 ms 2284 KB Output is correct
5 Correct 3 ms 2796 KB Output is correct
6 Correct 2 ms 2540 KB Output is correct
7 Correct 2 ms 2412 KB Output is correct
8 Correct 3 ms 2796 KB Output is correct
9 Correct 1 ms 1388 KB Output is correct
10 Correct 3 ms 3180 KB Output is correct
11 Correct 3 ms 3308 KB Output is correct
12 Correct 4 ms 3328 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 2 ms 2028 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 2 ms 2284 KB Output is correct
5 Correct 3 ms 2796 KB Output is correct
6 Correct 2 ms 2540 KB Output is correct
7 Correct 2 ms 2412 KB Output is correct
8 Correct 3 ms 2796 KB Output is correct
9 Correct 1 ms 1388 KB Output is correct
10 Correct 3 ms 3180 KB Output is correct
11 Correct 3 ms 3308 KB Output is correct
12 Correct 4 ms 3328 KB Output is correct
13 Correct 58 ms 34924 KB Output is correct
14 Correct 71 ms 46956 KB Output is correct
15 Correct 172 ms 57836 KB Output is correct
16 Correct 39 ms 27116 KB Output is correct
17 Correct 67 ms 33900 KB Output is correct
18 Correct 48 ms 21740 KB Output is correct
19 Correct 200 ms 61292 KB Output is correct
20 Correct 162 ms 50304 KB Output is correct
21 Correct 112 ms 41452 KB Output is correct
22 Correct 109 ms 43648 KB Output is correct
23 Correct 125 ms 63340 KB Output is correct
24 Correct 252 ms 63340 KB Output is correct
25 Correct 189 ms 53760 KB Output is correct
26 Correct 222 ms 59116 KB Output is correct
27 Correct 251 ms 62444 KB Output is correct