Submission #681841

#	Time	Username	Problem	Language	Result	Execution time	Memory
681841		bin9638	Kangaroo (CEOI16_kangaroo)	C++17	51 / 100	2086 ms	126064 KiB

kangaroo

#include<bits/stdc++.h>

using namespace std;
#define N  2010
#define ll long long
#define ii pair<int,int>
#define fs first
#define sc second
#define pb push_back
#define iii pair<int,ii>
#define int ll

const ll mod=1000000007;

void selfadd(int&u,int v)
{
    u=(u+v)%mod;
}

int dp[2][N][N][2],n,S,T;

int32_t main()
{
 //   freopen("A.inp","r",stdin);
   // freopen("A.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>S>>T;
    for(int i=S;i<=n;i++)
            dp[(n&1)][T][i][0]=dp[(n&1)][T][i][1]=1;
    // 0 <-
    // 1 ->
    for(int i=n-1;i>=2;i--)
    {
        //memset(dp[(i&1)],0,sizeof(dp[(i&1)]));
        for(int pos=1;pos<=i;pos++)
                for(int j=1;j<=i;j++)
                    if(j!=pos)
                    {
                        //0 <-
                        dp[(i&1)][pos][j][0]=dp[((i+1)&1)][pos+1][min(j,pos)][1];
                        if(j>=pos)
                            selfadd(dp[i&1][pos][j][0],dp[((i+1)&1)][pos][j][1]-dp[((i+1)&1)][pos][pos][1]);
                        //1 ->

                        dp[(i&1)][pos][j][1]=(dp[((i+1)&1)][pos][i+1][0]-dp[((i+1)&1)][pos][max(pos,j)][0])%mod;
                        if(j<=pos)
                            selfadd(dp[(i&1)][pos][j][1],dp[((i+1)&1)][pos+1][pos+1][0]-dp[((i+1)&1)][pos+1][j][0]);

                        selfadd(dp[(i&1)][pos][j][0],dp[(i&1)][pos][j-1][0]);
                        selfadd(dp[(i&1)][pos][j][1],dp[(i&1)][pos][j-1][1]);
                    }else
                    {
                        dp[(i&1)][pos][j][0]=dp[(i&1)][pos][j-1][0];
                        dp[(i&1)][pos][j][1]=dp[(i&1)][pos][j-1][1];
                    }
    }
    cout<<(dp[0][1][2][0]+dp[0][2][1][1]+mod*mod)%mod;
    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 30 / 30
• Subtask 3: 15 / 15
• Subtask 4: 0 / 49