제출 #422206

#제출 시각아이디문제언어결과실행 시간메모리
422206julian33캥거루 (CEOI16_kangaroo)C++14
0 / 100
1 ms332 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int mxN=2e3+5,mod=1e9+7;

ll dp[mxN][mxN][2],pref[mxN][mxN],suff[mxN][mxN];

int main(){
    cin.sync_with_stdio(0); cin.tie(0);
    #ifdef LOCAL
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    
    int n,s,f; cin>>n>>s>>f;
    dp[s][1][0]=dp[s][1][1]=1;
    for(int j=1;j<=n;j++){
        for(int i=1;i<=n && j>1;i++){
            if(i==s)
                continue;
            dp[i][j][1]=(pref[i-1][j-1]-dp[i][max(0,j-2)][1]+mod)%mod;
            dp[i][j][0]=(suff[i+1][j-1]-dp[i][max(0,j-2)][0]+mod)%mod;
        }
        for(int i=1;i<=n;i++)
            pref[i][j]=(pref[i-1][j]+dp[i][j][0])%mod;
        for(int i=n;i>=1;i--)
            suff[i][j]=(suff[i+1][j]+dp[i][j][1])%mod;
        // for(int i=1;i<=n;i++){
        //     cout<<dp[i][j][0]<<","<<dp[i][j][1]<<" ";
        // }
        // cout<<"\n";
    }
    cout<<(dp[f][n][0]+dp[f][n][1])%mod<<"\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...