oj.uz

Submission #696532

# Submission time Handle Problem Language Result Execution time Memory
696532 2023-02-06T17:48:07 Z lucri Ruins 3 (JOI20_ruins3) C++17
58 / 100
 290 ms 524288 KB 
#include <bits/stdc++.h>
using namespace std;
const long long MOD=1000000007;
int ma[610][610][610][2];
inline long long putere(long long a,long long b)
{
    if(b==0)
        return 1;
    long long p=putere(a,b/2);
    p*=p;
    p%=MOD;
    if(b%2)
    {
        p*=a;
        p%=MOD;
    }
    return p;
}
long long fact[610],comb[610][610];
inline void factorial()
{
    fact[0]=1;
    for(long long i=1;i<=600;++i)
        fact[i]=fact[i-1]*i%MOD;
}
inline long long combinari(long long n,long long m)
{
    long long ans=1;
    ans=fact[n];
    ans*=putere(fact[m],MOD-2);
    ans%=MOD;
    ans*=putere(fact[n-m],MOD-2);
    ans%=MOD;
    return ans;
}
long long n,v[610];
inline long long raspunde(long long step,long long nrstack,long long ppoz,bool exista)
{
    if(ma[step][nrstack][ppoz][exista]!=-1)
        return ma[step][nrstack][ppoz][exista];
    if(step==n)
    {
        ma[step][nrstack][ppoz][exista]=1;
        return 1;
    }
    long long ans=0;
    long long ramas=n-step-nrstack;
    long long posibileInceput=v[ppoz]-1-(2*step-step+ppoz-1-nrstack);
    if(exista==false)
    {
        if(ramas>=3)
            ans=(ans+comb[ramas-1][2]*raspunde(step+1,nrstack+1,ppoz,false))%MOD;
        if(ramas>=2)
            ans=(ans+(ramas-1)*raspunde(step+1,nrstack+1,ppoz,true))%MOD;
        if(posibileInceput>=2&&nrstack>=1)
            ans=(ans+comb[posibileInceput][2]*raspunde(step+1,nrstack-1,ppoz,false))%MOD;
        if(posibileInceput&&nrstack>=1&&ramas>=1)
        {
            if(ramas-1)
                ans=(ans+posibileInceput*(ramas-1)%MOD*raspunde(step+1,nrstack,ppoz,false))%MOD;
            ans=(ans+posibileInceput*raspunde(step+1,nrstack,ppoz,true))%MOD;
        }
        else if(posibileInceput&&ramas>=1)
        {
            if(step==n-1)
            {
                ma[step][nrstack][ppoz][exista]=1;
                return 1;
            }
            if(ramas-1)
                ans=(ans+posibileInceput*(ramas-1)%MOD*raspunde(step+1,nrstack,ppoz,false))%MOD;
            long long q=putere(comb[n-ppoz][step+1-ppoz],MOD-2);
            for(int newppoz=ppoz+1;newppoz<=step+2;++newppoz)
                ans=(ans+comb[n-newppoz][step+2-newppoz]*q%MOD*posibileInceput%MOD*raspunde(step+1,nrstack,newppoz,false))%MOD;
        }
    }
    else
    {
        if(ramas>=2)
            ans=(ans+comb[ramas][2]*raspunde(step+1,nrstack+1,ppoz,true))%MOD;
        if(posibileInceput>=2)
        {
            if(nrstack>=2)
                ans=(ans+comb[posibileInceput][2]*raspunde(step+1,nrstack-1,ppoz,true))%MOD;
            else
            {
                if(step==n-1)
                {
                    ma[step][nrstack][ppoz][exista]=1;
                    return 1;
                }
                long long q=putere(comb[n-ppoz][step+1-ppoz],MOD-2);
                for(int newppoz=ppoz+1;newppoz<=step+2;++newppoz)
                    ans=(ans+comb[n-newppoz][step+2-newppoz]*q%MOD*comb[posibileInceput][2]%MOD*raspunde(step+1,nrstack-1,newppoz,false))%MOD;
            }
        }
        if(posibileInceput&&ramas>=1)
            ans=(ans+posibileInceput*ramas%MOD*raspunde(step+1,nrstack,ppoz,true))%MOD;
    }
    ma[step][nrstack][ppoz][exista]=ans;
    return ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    factorial();
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>v[i];
    for(int i=0;i<=n;++i)
        for(int j=0;j<=i;++j)
            comb[i][j]=combinari(i,j);
    for(int i=0;i<=n;++i)
        for(int j=0;j<=n;++j)
            for(int k=0;k<=n;++k)
                for(int l=0;l<=1;++l)
                    ma[i][j][k][l]=-1;
    cout<<raspunde(0,0,1,false);
    return 0;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 1236 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 1236 KB Output is correct
6 Correct 1 ms 1236 KB Output is correct
7 Correct 1 ms 1236 KB Output is correct
8 Correct 1 ms 1236 KB Output is correct
9 Correct 1 ms 1236 KB Output is correct
10 Correct 1 ms 1236 KB Output is correct
11 Correct 9 ms 17492 KB Output is correct
12 Correct 8 ms 17492 KB Output is correct
13 Correct 8 ms 17492 KB Output is correct
14 Correct 9 ms 17480 KB Output is correct
15 Correct 9 ms 17492 KB Output is correct
16 Correct 9 ms 17456 KB Output is correct
17 Correct 9 ms 17492 KB Output is correct
18 Correct 10 ms 17492 KB Output is correct
19 Correct 11 ms 17492 KB Output is correct
20 Correct 11 ms 17424 KB Output is correct

Subtask #3
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 1236 KB Output is correct
3 Correct 1 ms 1236 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 1236 KB Output is correct
6 Correct 1 ms 1236 KB Output is correct
7 Correct 1 ms 1236 KB Output is correct
8 Correct 1 ms 1236 KB Output is correct
9 Correct 1 ms 1236 KB Output is correct
10 Correct 1 ms 1236 KB Output is correct
11 Correct 9 ms 17492 KB Output is correct
12 Correct 8 ms 17492 KB Output is correct
13 Correct 8 ms 17492 KB Output is correct
14 Correct 9 ms 17480 KB Output is correct
15 Correct 9 ms 17492 KB Output is correct
16 Correct 9 ms 17456 KB Output is correct
17 Correct 9 ms 17492 KB Output is correct
18 Correct 10 ms 17492 KB Output is correct
19 Correct 11 ms 17492 KB Output is correct
20 Correct 11 ms 17424 KB Output is correct
21 Runtime error 290 ms 524288 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -