Submission #44194

#	Time	Username	Problem	Language	Result	Execution time	Memory
44194		igzi	Kangaroo (CEOI16_kangaroo)	C++17	51 / 100	371 ms	259104 KiB

kangaroo

#include <bits/stdc++.h>
#define mod 1000000007
#define maxN 202

using namespace std;

long long dp[2][maxN][maxN][maxN],a[2][maxN][maxN],n,i,j,k,s,e,x;

int main()
{
    cin>>n>>s>>e;
    dp[0][1][1][1]=dp[1][1][1][1]=1;
    a[0][1][1]=a[1][1][1]=1;
    for(i=2;i<=n;i++){
        for(j=1;j<=i;j++){
            for(k=1;k<=i;k++){
                if(j==k) {dp[0][j][k][i]=dp[1][j][k][i]=0; continue;}
                if(j<k) x=k-1;
                else x=k;
                dp[0][j][k][i]=a[1][j][x];
                dp[0][j][k][i]%=mod;
                dp[1][j][k][i]=a[0][j-1][x];
                dp[1][j][k][i]%=mod;
                //if(i==2 && j==2 && k==1) cout<<dp[1][j][k][i]<<endl;
                //if(i==3) cout<<a[1][1][1]<<" "<<dp[1][1][2][2]<<" "<<dp[1][2][1][2]<<endl;
            }
        }
        for(j=1;j<=i;j++){
            a[0][0][j]=a[1][i+1][j]=0;
            for(k=1;k<=i;k++){
                a[0][k][j]=a[0][k-1][j]+dp[0][k][j][i];
                a[0][k][j]%=mod;
            }
            for(k=i;k>0;k--){
                a[1][k][j]=a[1][k+1][j]+dp[1][k][j][i];
                a[1][k][j]%=mod;
            }
        }
    }
    cout<<(dp[0][s][e][n]+dp[1][s][e][n])%mod<<endl;
    return 0;
}

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