Submission #728029

#	Time	Username	Problem	Language	Result	Execution time	Memory
728029		ilia_rr	Ruins 3 (JOI20_ruins3)	C++17	100 / 100	465 ms	348 KiB

ruins3

// بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيمِ
// Written by Ilia Rahbar

// #pragma GCC optimize ("O3,no-stack-protector,unroll-loops,fast-math")
// #pragma GCC target ("abm,bmi,bmi2,tbm,avx2")

#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define sz(x) int(x.size())
#define ai(x) array <int, x>
#define be(x) x.begin(), x.end()
#define pb push_back
#define el '\n'
#define sp ' '
#define fi first 
#define se second

const int M = 1e9 + 7, N = 605;

int n, a[N * 2], x, z, f[N] = {1}, dp[N] = {1}, fact[N] = {1, 1}, invfact[N] = {1, 1};

int pwr(int a, int b)
{
    if (!b)
        return 1;
    
    int x = pwr(a, b / 2);

    return x * x % M * (b & 1 ? a : 1) % M;
}

int c(int a, int b)
{
    return fact[a] * invfact[b] % M * invfact[a - b] % M;
}

int32_t main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    for (int i = 2; i < N; i++)
        fact[i] = fact[i-1] * i % M, invfact[i] = pwr(fact[i], M - 2);

    cin >> n;

    for (int i = 0; i < n; i++)
        cin >> x, a[x] = 1;

    for (int i = 1; i < N; i++)
        for (int j = 0; j < i; j++)
            f[i] = (f[i] + f[j] * f[i - j - 1] % M * c(i - 1, j) % M * (i - j + 1) % M) % M;

    for (int i = 1; i <= n * 2; i++)
    {
        if (a[n * 2 - i + 1])
        {
            for (int x = i - z; x; x--)
            {
                for (int y = 0; y < x; y++)
                {
                    dp[x] = (dp[x] + dp[y] * f[x - y - 1] % M * c(i - z - 1 - y, x - y - 1) % M * (x - y + 1) % M) % M;
                }
            }
        }

        else
        {
            for (int x = 0; x <= n; x++) 
                dp[x] = max(int(0), dp[x] * (x - z)) % M;

            z++;
        }
    }
    

    cout << dp[n] * pwr(2, (M - 2) * n) % M;
}

• Subtask 1: 6 / 6
• Subtask 2: 52 / 52
• Subtask 3: 42 / 42