Submission #681830

#	Time	Username	Problem	Language	Result	Execution time	Memory
681830		bin9638	Kangaroo (CEOI16_kangaroo)	C++17	51 / 100	67 ms	66244 KiB

kangaroo

#include<bits/stdc++.h>

using namespace std;
#define N  210
#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[N][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;
    if(n>300)
    {
        return 0;
    }
    for(int i=S;i<=n;i++)
            dp[n][T][i][0]=dp[n][T][i][1]=1;
    // 0 <-
    // 1 ->
    for(int i=n-1;i>=2;i--)
        for(int pos=1;pos<=i;pos++)
                for(int j=1;j<=i;j++)
                    if(j!=pos)
                    {
                        //0 <-
                        selfadd(dp[i][pos][j][0],dp[i+1][pos+1][min(j,pos)][1]);
                        if(j>=pos)
                            selfadd(dp[i][pos][j][0],dp[i+1][pos][j][1]-dp[i+1][pos][pos][1]);
                        //1 ->

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

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

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