oj.uz

Submission #526555

# Submission time Handle Problem Language Result Execution time Memory
526555 2022-02-15T08:10:35 Z radal Ruins 3 (JOI20_ruins3) C++14
58 / 100
 10 ms 6332 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2,fma")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
const long long int N = 6e2+20,mod = 1e9+7,inf = 1e18+10,maxm= (1 << 21);
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}

inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k >>= 1;
    }
    return z;
}
bool b[N];
int dp[N],pre[N][N],c[N][N];
int main(){
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    rep(i,0,n){
        int x;
        cin >> x;
        b[x] = 1;
    }
    int m = n * 2;
    rep(i,0,m+1)
        c[0][i] = 1;
    rep(i,1,m+1)
        rep(j,i,m+1)
            c[i][j] = mkay(c[i-1][j-1],c[i][j-1]);
    dp[0] = 1;
    rep(i,1,n+1){
        rep(j,1,i+1){
            dp[i] = mkay(dp[i],1ll*c[j-1][i-1]*dp[j-1]%mod*dp[i-j]%mod*(i-j+2)%mod);
        }
    }
    int c0 = 0,c1 = 0;
    pre[m+1][0] = 1;
    repr(i,m,1){
        if (b[i]){
            rep(j,0,c1+2){
                pre[i][j] = pre[i+1][j];
                rep(y,1,j+1){
                    pre[i][j] = mkay(pre[i][j],1ll*pre[i+1][y-1]*dp[j-y]%mod*c[j-y][c1-y+1]%mod*(j-y+2)%mod);
                }
            }
            c1++;
        }
        else{
            rep(j,0,c1+1){
                pre[i][j] = 1ll*pre[i+1][j]*max(0,-c0+j)%mod;
            }
            c0++;
        }
    }
    cout << 1ll*pre[1][n]*poww(poww(2,n),mod-2)%mod;
    return 0;
 }

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 320 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 452 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 432 KB Output is correct
9 Correct 1 ms 316 KB Output is correct
10 Correct 1 ms 316 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 320 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 452 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 432 KB Output is correct
9 Correct 1 ms 316 KB Output is correct
10 Correct 1 ms 316 KB Output is correct
11 Correct 1 ms 840 KB Output is correct
12 Correct 1 ms 844 KB Output is correct
13 Correct 2 ms 844 KB Output is correct
14 Correct 1 ms 844 KB Output is correct
15 Correct 1 ms 844 KB Output is correct
16 Correct 2 ms 844 KB Output is correct
17 Correct 1 ms 844 KB Output is correct
18 Correct 2 ms 836 KB Output is correct
19 Correct 1 ms 844 KB Output is correct
20 Correct 1 ms 844 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 320 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 452 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 432 KB Output is correct
9 Correct 1 ms 316 KB Output is correct
10 Correct 1 ms 316 KB Output is correct
11 Correct 1 ms 840 KB Output is correct
12 Correct 1 ms 844 KB Output is correct
13 Correct 2 ms 844 KB Output is correct
14 Correct 1 ms 844 KB Output is correct
15 Correct 1 ms 844 KB Output is correct
16 Correct 2 ms 844 KB Output is correct
17 Correct 1 ms 844 KB Output is correct
18 Correct 2 ms 836 KB Output is correct
19 Correct 1 ms 844 KB Output is correct
20 Correct 1 ms 844 KB Output is correct
21 Runtime error 10 ms 6332 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -