oj.uz

Submission #906689

# Submission time Handle Problem Language Result Execution time Memory
906689 2024-01-14T18:03:21 Z manizare Ruins 3 (JOI20_ruins3) C++14
58 / 100
 2 ms 604 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops") 
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define ld long double
#define int long long
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= (b);i++)
#define per(i , a , b) for(int i=a;i >= (b);i--)
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 100 , maxw= 1e3 + 10,  lg = 18 , inf = 1e18 , mod= 1e9 + 7 ;
int dp2[maxn][maxn] , dp[maxn][maxn] , f[maxn] , inv[maxn] , pr[maxn] , a[maxn] , sm[maxn][maxn] ;

int po(int a, int b){
    if(b==0)return 1;
    int v =po(a,b/2) ;
    v = v*v%mod ;
    if(b&1) v =v*a %mod ;
    return v; 
}
int c(int n , int k){
    if(n < k || k < 0)return 0 ;
    return f[n] * inv[k]%mod * inv[n-k]%mod ; 
}

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    f[0] = 1;
    rep(i , 1, maxn-1){
        f[i] = f[i-1] * i % mod  ;
    }
    inv[maxn-1] = po(f[maxn-1] , mod-2); 
    per(i , maxn-2 , 0){
        inv[i] = inv[i+1] * (i+1) % mod ;
    }
    int n;cin >> n ;
    rep(i , 1, n){
        cin >> a[i] ; 
    }
    pr[0] = a[1] -1 ;
    rep(i , 1, n){
        pr[i] = pr[i-1] + (a[i+1] - a[i] - 1) ;
    }
    int a2 = po(2, mod-2); 
    dp2[1][0] = 1; dp2[1][1] = a2 ;
    rep(i , 1 , n){
        rep(j , 1, n){
            dp2[i+1][j+1] = (dp2[i+1][j+1] + a2*dp2[i][j] %mod)%mod ;
            dp2[i+1][j-1] = (dp2[i+1][j-1] + a2*dp2[i][j]%mod)%mod ;
            dp2[i+1][j] = (dp2[i+1][j] + dp2[i][j]%mod)%mod ;
        }
    }
    dp[0][0]= 1;
    rep(i , 0, n){
        rep(j , 1, i+2){
            sm[i][j] = (sm[i][j] + sm[i][j-1])%mod ;
        }
        rep(j , 0 , i){
            dp[i][j] = (dp[i][j] + sm[i][j] * inv[i-j]%mod)%mod ;
            rep(k ,  1 , n-i){
                int x = dp[i][j] * c(pr[j]-(i) , k) %mod * f[k] % mod * dp2[k][0] %mod ;                   
                dp[i+k][j] = (dp[i+k][j] + x) %mod ; 
                x = x * k%mod * f[i+k-1-j]%mod ;
                sm[i+k][j] = (sm[i+k][j] + x)%mod ; 
                dp[i+k][j] = (dp[i+k][j]-x*inv[i+k-j]%mod+mod)%mod ;
            }
        }
    }
    cout << dp[n][n]%mod << "\n";
}
/*

*/

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 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 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 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 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 2 ms 600 KB Output is correct
19 Correct 2 ms 600 KB Output is correct
20 Correct 2 ms 600 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 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 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 600 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 1 ms 604 KB Output is correct
18 Correct 2 ms 600 KB Output is correct
19 Correct 2 ms 600 KB Output is correct
20 Correct 2 ms 600 KB Output is correct
21 Runtime error 2 ms 600 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -