oj.uz

Submission #1047071

# Submission time Handle Problem Language Result Execution time Memory
1047071 2024-08-07T08:32:31 Z 정민찬(#11024) Ruins 3 (JOI20_ruins3) C++17
58 / 100
 17 ms 37708 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

const ll mod = 1e9 + 7;

ll fastpow(ll a, ll b) {
    ll ret = 1;
    while (b) {
        if (b % 2 == 1) ret = ret * a % mod;
        b /= 2;
        a = a * a % mod;
    }
    return ret;
}

ll dp[300][300][610];
ll br[610][610];
ll com[610];
ll fac[610], inv[610];

ll P(ll n, ll r) {
    if (n < r) return 0;
    return fac[n] * inv[n-r] % mod;
}

int main() {
    ios_base :: sync_with_stdio(false); cin.tie(NULL);
    com[0] = 1;
    com[1] = 2;
    br[1][1] = 1;
    br[1][2] = 1;
    for (ll i=2; i<=600; i++) {
        ll sum = 0;
        for (ll j=i-1; j<=i*2-1; j++) {
            sum = (sum + br[i-1][j]) % mod;
            br[i][j+1] = sum;
            com[i] = (com[i] + sum) % mod;
        }
    }
    fac[0] = 1;
    for (ll i=1; i<=600; i++) {
        fac[i] = fac[i-1] * i % mod;
    }
    inv[600] = fastpow(fac[600], mod-2);
    for (ll i=600-1; i>=0; i--) {
        inv[i] = inv[i+1] * (i+1) % mod;
    }
    ll N;
    cin >> N;
    vector<ll> a(N);
    vector<ll> chk(2*N, 0);
    for (ll i=0; i<N; i++) {
        cin >> a[i];
        a[i] --;
        chk[a[i]] = 1;
    }
    dp[2*N][0][0] = 1;
    for (ll i=2*N-1; i>=0; i--) {
        ll cnt = 2*N - i;
        if (!chk[i]) {
            for (ll j=0; j<=cnt-1; j++) {
                for (ll k=j; k<2*j; k++) {
                    dp[i][j][k+1] += dp[i+1][j][k] * (2*j - k) % mod;
                    dp[i][j][k+1] %= mod;
                }
            }
        }
        else {
            for (ll j=0; j<=cnt-1; j++) {
                for (ll k=j; k<=min(cnt-1, 2*j); k++) {
                    if (cnt - k > N-j) continue;
                    if (cnt - k == N-j) {
                        dp[i][N][cnt] += dp[i+1][j][k] * fac[N-j-1] % mod
                                         * com[N-j-1] % mod * (N-j+1) % mod;
                        dp[i][N][cnt] %= mod;
                    }
                    else {
                        dp[i][j][k] += dp[i+1][j][k];
                        dp[i][j][k] %= mod;
                        for (ll l=1; l<=cnt-k; l++) {
                            dp[i][j+l][k+l] += dp[i+1][j][k] * P(cnt-k-1, l-1) % mod
                                                 * com[l-1] % mod * (l+1) % mod;
                            dp[i][j+l][k+l] %= mod;
                        }
                    }
                }
            }
        }
    }
    ll ans = dp[0][N][2*N];
    ll inv2 = fastpow(2, mod-2);
    for (ll i=0; i<N; i++) {
        ans = ans * inv2 % mod;
    }
    cout << ans << '\n';
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 2 ms 7772 KB Output is correct
3 Correct 2 ms 7772 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 2 ms 7516 KB Output is correct
6 Correct 2 ms 7800 KB Output is correct
7 Correct 2 ms 7260 KB Output is correct
8 Correct 2 ms 8028 KB Output is correct
9 Correct 3 ms 8024 KB Output is correct
10 Correct 2 ms 8280 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 2 ms 7772 KB Output is correct
3 Correct 2 ms 7772 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 2 ms 7516 KB Output is correct
6 Correct 2 ms 7800 KB Output is correct
7 Correct 2 ms 7260 KB Output is correct
8 Correct 2 ms 8028 KB Output is correct
9 Correct 3 ms 8024 KB Output is correct
10 Correct 2 ms 8280 KB Output is correct
11 Correct 17 ms 31248 KB Output is correct
12 Correct 11 ms 30764 KB Output is correct
13 Correct 12 ms 31772 KB Output is correct
14 Correct 12 ms 30808 KB Output is correct
15 Correct 11 ms 27996 KB Output is correct
16 Correct 12 ms 29528 KB Output is correct
17 Correct 8 ms 21596 KB Output is correct
18 Correct 15 ms 37708 KB Output is correct
19 Correct 13 ms 36700 KB Output is correct
20 Correct 14 ms 36616 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 2 ms 7772 KB Output is correct
3 Correct 2 ms 7772 KB Output is correct
4 Correct 2 ms 7260 KB Output is correct
5 Correct 2 ms 7516 KB Output is correct
6 Correct 2 ms 7800 KB Output is correct
7 Correct 2 ms 7260 KB Output is correct
8 Correct 2 ms 8028 KB Output is correct
9 Correct 3 ms 8024 KB Output is correct
10 Correct 2 ms 8280 KB Output is correct
11 Correct 17 ms 31248 KB Output is correct
12 Correct 11 ms 30764 KB Output is correct
13 Correct 12 ms 31772 KB Output is correct
14 Correct 12 ms 30808 KB Output is correct
15 Correct 11 ms 27996 KB Output is correct
16 Correct 12 ms 29528 KB Output is correct
17 Correct 8 ms 21596 KB Output is correct
18 Correct 15 ms 37708 KB Output is correct
19 Correct 13 ms 36700 KB Output is correct
20 Correct 14 ms 36616 KB Output is correct
21 Runtime error 8 ms 9048 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -