oj.uz

Submission #749212

# Submission time Handle Problem Language Result Execution time Memory
749212 2023-05-27T14:45:28 Z Lucpp Festivals in JOI Kingdom 2 (JOI23_festival2) C++17
37 / 100
 9000 ms 1748 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie();
    int n; ll mod;
    cin >> n >> mod;
    vector<vector<ll>> binom(n+1, vector<ll>(n+1));
    for(int i = 0; i <= n; i++){
        binom[i][0] = 1;
        for(int j = 1; j <= i; j++){
            binom[i][j] = (binom[i-1][j-1] + binom[i-1][j]) % mod;
        }
    }
    vector<ll> fact(n+1);
    fact[0] = 1;
    for(int i = 1; i <= n; i++) fact[i] = (fact[i-1]*i) % mod;

    vector<vector<ll>> dp(n+1, vector<ll>(n+1));
    dp[n][n] = 1;
    for(int a = n-1; a >= 0; a--){
        for(int b = a; b >= 0; b--){
            ll res = 0;
            for(int k = a+1; k <= n; k++){
                for(int l = a+1; l <= k; l++){
                    ll cnt = 0;
                    if(k == l){
                        for(int e = 1; e <= l-b; e++){
                            ll add = binom[l-b-1][e-1] * fact[e] % mod;
                            for(int up = 0; up < l-b-e; up++){
                                add = add * (2*(n-l)+up) % mod;
                            }
                            cnt = (cnt + add) % mod;
                            // cerr << "# " << binom[l-b][e-1] << " " << fact[e] << "\n";
                        }
                    }
                    else
                    for(int ek = 1; ek <= l-b; ek++){
                        for(int el = 1; ek+el <= l-b; el++){
                            ll add = binom[l-b-1][ek+el-1] * binom[ek+el-1][el] % mod;
                            add = add * fact[ek] % mod;
                            add = add * fact[el] % mod;
                            for(int up = 0; up < l-b-el-ek; up++){
                                add = add * (2*(n-l)-1+up) % mod;
                            }
                            cnt = (cnt + add) % mod;
                        }
                    }
                    res = (res + cnt * dp[k][l]) % mod;
                    // cerr << a << " " << b << " " << k << " " << l << "  ->  " << cnt << " " << cnt*dp[k][l] << "\n";
                }
            }
            dp[a][b] = res;
        }
    }
    ll total = 1;
    for(int i = 0; i < n; i++) total = total * (2*i+1) % mod;
    // cerr << dp[0][0] << "\n";
    cout << (total - dp[0][0] + mod) % mod << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 1 ms 316 KB Output is correct
13 Correct 1 ms 372 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 1 ms 316 KB Output is correct
13 Correct 1 ms 372 KB Output is correct
14 Correct 2 ms 212 KB Output is correct
15 Correct 149 ms 316 KB Output is correct
16 Correct 120 ms 316 KB Output is correct
17 Correct 6 ms 212 KB Output is correct
18 Correct 2 ms 212 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 1 ms 316 KB Output is correct
13 Correct 1 ms 372 KB Output is correct
14 Correct 2 ms 212 KB Output is correct
15 Correct 149 ms 316 KB Output is correct
16 Correct 120 ms 316 KB Output is correct
17 Correct 6 ms 212 KB Output is correct
18 Correct 2 ms 212 KB Output is correct
19 Execution timed out 9016 ms 1748 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 1 ms 316 KB Output is correct
13 Correct 1 ms 372 KB Output is correct
14 Correct 2 ms 212 KB Output is correct
15 Correct 149 ms 316 KB Output is correct
16 Correct 120 ms 316 KB Output is correct
17 Correct 6 ms 212 KB Output is correct
18 Correct 2 ms 212 KB Output is correct
19 Execution timed out 9016 ms 1748 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 320 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 1 ms 316 KB Output is correct
13 Correct 1 ms 372 KB Output is correct
14 Correct 2 ms 212 KB Output is correct
15 Correct 149 ms 316 KB Output is correct
16 Correct 120 ms 316 KB Output is correct
17 Correct 6 ms 212 KB Output is correct
18 Correct 2 ms 212 KB Output is correct
19 Execution timed out 9016 ms 1748 KB Time limit exceeded
20 Halted 0 ms 0 KB -