제출 #44194

#제출 시각아이디문제언어결과실행 시간메모리
44194igzi캥거루 (CEOI16_kangaroo)C++17
51 / 100
371 ms259104 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...