oj.uz

Submission #1041979

# Submission time Handle Problem Language Result Execution time Memory
1041979 2024-08-02T11:35:30 Z hotboy2703 Ruins 3 (JOI20_ruins3) C++17
58 / 100
 1 ms 2652 KB 
#include<bits/stdc++.h>
using ll = long long;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll INF = 1e9;
const ll MAXN = 610;
ll dp[MAXN][MAXN];
ll fac[2*MAXN],fiv[2*MAXN];
const ll MOD = 1e9+7;
ll p(ll x,ll y){
    ll res = 1;
    for (;y;y>>=1,x=x*x%MOD)if (y&1)res=res*x%MOD;
    return res;
}
ll inv(ll x){
    return p(x,MOD-2);
}
ll C(ll k,ll n){
    if (k > n || k < 0)return 0;
    return fac[n] * fiv[k] % MOD * fiv[n-k] % MOD;
}
ll ways[MAXN];
bool ok[2*MAXN];
int main(){
    ios_base::sync_with_stdio(0);cin.tie(nullptr);
    ll n;
    cin>>n;
    for (ll i = 1;i <= n;i ++){
        ll x;cin>>x;
        ok[x] = 1;
    }
    fac[0] = 1;
    for (ll i = 1;i <= 2*n;i ++)fac[i] = fac[i-1]*i%MOD;
    fiv[2*n] = inv(fac[2*n]);
    for (ll i = 2*n-1;i >= 0;i --)fiv[i] = fiv[i+1]*(i+1)%MOD;
    for (ll i = 0;i <= n;i ++)ways[i] = (C(i,2*i) * fac[i-1])%MOD;
    // cout<<ways[1]<<' '<<ways[2]<<'\n';
    ll a,b;dp[2*n+1][0] = 1;
    a=b=0;
    for (ll i = 2 * n;i >= 1;i --){
        if (ok[i]){
            a++;
            for (ll j = b;j <= a;j ++){
                for (ll k = b;k < j;k ++){
                    dp[i][j] += dp[i+1][k] * C(j - k - 1,a - k - 1) % MOD * ways[j-k];
                    dp[i][j] %= MOD;
                }
                dp[i][j] += dp[i+1][j];
                dp[i][j] %= MOD; 
            }
            
        }
        else{
            b++;
            for (ll j = b;j <= a;j ++){
                dp[i][j] = dp[i+1][j] * (j-(b-1)) % MOD;
            }
        }
        // for (ll j = 0;j <= n;j ++)cout<<dp[i][j]<<' ';
        // cout<<'\n';
    }
    cout<<dp[1][n] * inv(p(2,n)) % MOD;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 0 ms 2652 KB Output is correct
14 Correct 0 ms 2652 KB Output is correct
15 Correct 0 ms 2396 KB Output is correct
16 Correct 0 ms 2652 KB Output is correct
17 Correct 0 ms 2396 KB Output is correct
18 Correct 1 ms 2648 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 1 ms 2652 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 2652 KB Output is correct
12 Correct 0 ms 2396 KB Output is correct
13 Correct 0 ms 2652 KB Output is correct
14 Correct 0 ms 2652 KB Output is correct
15 Correct 0 ms 2396 KB Output is correct
16 Correct 0 ms 2652 KB Output is correct
17 Correct 0 ms 2396 KB Output is correct
18 Correct 1 ms 2648 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 1 ms 2652 KB Output is correct
21 Runtime error 1 ms 600 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -