oj.uz

Submission #684908

# Submission time Handle Problem Language Result Execution time Memory
684908 2023-01-22T20:06:21 Z lucaperju Ruins 3 (JOI20_ruins3) C++14
100 / 100
 5486 ms 17492 KB 
#include <bits/stdc++.h>
using namespace std;
const int mod=1000000007;
long long lgput (long long a, long long exp)
{
    long long rz=1;
    while(exp)
    {
        if(exp&1)
        {
            exp^=1;
            rz=(rz*1LL*a)%mod;
        }
        else
        {
            exp>>=1;
            a=(a*1LL*a)%mod;
        }
    }
    return rz;
}
int inv2;
long long cmb2 (int n)
{
    if(n<2)
        return 0;
    return n*(n-1LL)%mod*1LL*inv2%mod;
}
int v[605];
int dp[605][605][2][3][2]; /// 0=NU ; 1=URMEAZA ; 2=POATE
int main()
{
    ios_base::sync_with_stdio(false);
    dp[0][0][0][0][0]=1;
    inv2=lgput(2,mod-2);
    int n;
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>v[i];
        v[i]-=i;
    }
    for(int prefX=0;prefX<=n;++prefX)
    {
        int ci=prefX%2;
        int ni=1-ci;
        for(int i=0;i<=n;++i)
            for(int j=0;j<=n;++j)
                for(int b=0;b<=2;++b)
                    for(int c=0;c<=1;++c)
                        dp[i][j][ni][b][c]=0;
        for(int _=0;_<=n;++_)
        {
            if(_ > prefX)
                dp[_][0][ni][2][0] = ( dp[_][0][ni][2][0] + dp[_][0][ci][2][0]*1LL*(_ - prefX)%mod );
            if(dp[_][0][ni][2][0] >= mod)
                dp[_][0][ni][2][0] -= mod;

            dp[_][0][ci][0][0] = (dp[_][0][ci][0][0] + dp[_][0][ci][2][0]);
            if(dp[_][0][ci][0][0] >= mod)
                dp[_][0][ci][0][0] -= mod;
        }
        for(int _=0;_<=n;++_)
            for(int x=0;x<=n;++x)
            {
                ++x;
                dp[_][x-1][ci][0][0] = (dp[_][x-1][ci][0][0] + dp[_][x][ci][0][1]);
                if(dp[_][x-1][ci][0][0] >= mod)
                    dp[_][x-1][ci][0][0] -= mod;
                if(x>=2) {
                    dp[_][x-1][ci][1][0] = (dp[_][x-1][ci][1][0] + dp[_][x][ci][1][1]);
                    if(dp[_][x-1][ci][1][0] >= mod)
                        dp[_][x-1][ci][1][0] -= mod;
                }
                else {
                    dp[_][x-1][ni][2][0] = (dp[_][x-1][ni][2][0] + dp[_][x][ci][1][1]);
                    if(dp[_][x-1][ni][2][0] >= mod)
                        dp[_][x-1][ni][2][0] -= mod;
                }
                --x;

                int dpc = dp[_][x][ci][0][0];
                int cate=v[prefX+1] - _;

                dp[_+2][x+0][ci][0][1] = (dp[_+2][x+0][ci][0][1] + dpc*1LL*cmb2(cate)%mod);
                if(dp[_+2][x+0][ci][0][1] >= mod)
                    dp[_+2][x+0][ci][0][1] -= mod;

                dp[_+1][x+1][ci][0][1] = (dp[_+1][x+1][ci][0][1] + dpc*1LL*cate%mod);
                if(dp[_+1][x+1][ci][0][1] >= mod)
                    dp[_+1][x+1][ci][0][1] -= mod;
                dp[_+1][x+1][ci][1][1] = (dp[_+1][x+1][ci][1][1] + dpc*1LL*cate%mod);
                if(dp[_+1][x+1][ci][1][1] >= mod)
                    dp[_+1][x+1][ci][1][1] -= mod;

                dp[_+0][x+2][ci][0][1] = (dp[_+0][x+2][ci][0][1] + dpc*1LL*inv2%mod);
                if(dp[_+0][x+2][ci][0][1] >= mod)
                    dp[_+0][x+2][ci][0][1] -= mod;
                dp[_+0][x+2][ci][1][1] = (dp[_+0][x+2][ci][1][1] + dpc);
                if(dp[_+0][x+2][ci][1][1] >= mod)
                    dp[_+0][x+2][ci][1][1] -= mod;

                dpc = dp[_][x][ci][1][0];

                dp[_+2][x+0][ci][1][1] = (dp[_+2][x+0][ci][1][1] + dpc*1LL*cmb2(cate)%mod);
                if(dp[_+2][x+0][ci][1][1] >= mod)
                    dp[_+2][x+0][ci][1][1] -= mod;

                dp[_+1][x+1][ci][1][1] = (dp[_+1][x+1][ci][1][1] + dpc*1LL*cate%mod);
                if(dp[_+1][x+1][ci][1][1] >= mod)
                    dp[_+1][x+1][ci][1][1] -= mod;

                dp[_+0][x+2][ci][1][1] = (dp[_+0][x+2][ci][1][1] + dpc*1LL*inv2%mod);
                if(dp[_+0][x+2][ci][1][1] >= mod)
                    dp[_+0][x+2][ci][1][1] -= mod;
            }
    }
    cout<<dp[n][0][n&1][0][0];
    return 0;
}

Subtask #1
6.0 / 6.0

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

Subtask #2
52.0 / 52.0

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

Subtask #3
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 5 ms 724 KB Output is correct
12 Correct 5 ms 768 KB Output is correct
13 Correct 5 ms 768 KB Output is correct
14 Correct 5 ms 724 KB Output is correct
15 Correct 5 ms 724 KB Output is correct
16 Correct 6 ms 768 KB Output is correct
17 Correct 6 ms 724 KB Output is correct
18 Correct 6 ms 772 KB Output is correct
19 Correct 5 ms 768 KB Output is correct
20 Correct 7 ms 768 KB Output is correct
21 Correct 5198 ms 17444 KB Output is correct
22 Correct 5195 ms 17444 KB Output is correct
23 Correct 5298 ms 17452 KB Output is correct
24 Correct 5348 ms 17476 KB Output is correct
25 Correct 5486 ms 17456 KB Output is correct
26 Correct 5244 ms 17452 KB Output is correct
27 Correct 5190 ms 17464 KB Output is correct
28 Correct 5155 ms 17448 KB Output is correct
29 Correct 4900 ms 17448 KB Output is correct
30 Correct 5286 ms 17448 KB Output is correct
31 Correct 5254 ms 17492 KB Output is correct
32 Correct 5327 ms 17448 KB Output is correct
33 Correct 5264 ms 17452 KB Output is correct
34 Correct 5233 ms 17448 KB Output is correct
35 Correct 5247 ms 17456 KB Output is correct
36 Correct 5435 ms 17452 KB Output is correct