Submission #1323842

#TimeUsernameProblemLanguageResultExecution timeMemory
1323842aedmhsnKangaroo (CEOI16_kangaroo)C++20
0 / 100
0 ms332 KiB

#include <bits/stdc++.h>

#define ll long long
#define ld long double


using namespace std;



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

// solve problem (no tutorial)
// take at least 15 mins explaining solution to yourself

ll dp[mxN+5][2][mxN+5];

void go(){

    ll n, cs, cf;
    cin >> n >> cs >> cf;

    for(int i=n; i>=1; i--){
        for(int j=0; j<2; j++){
            for(int k=0; k<=n; k++){
                ll &ret = dp[i][j][k];
                if(i == n){
                    ret = 1;
                    continue;
                }
                if(j == 0){
                    ret = dp[i+1][1][k-1];
                }
                else{
                    ll len = (n-(i-1)-k)-1;
                    ret = dp[i+1][0][min(n, k+len-1)];
                    if(k-1 >= 0){
                        ret = (ret - dp[i+1][0][k] + MOD)%MOD;
                    }
                }
            }
            for(int k=1; k<=n; k++){
                dp[i][j][k] = (dp[i][j][k] + dp[i][j][k-1])%MOD;
            }
        }
    }
    ll ans = (dp[2][0][n-cs-(cf > cs)] + dp[2][1][n-cs-(cf > cs)])%MOD;
    cout << ans;



}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int tc=1;
    // cin >> tc;
    while(tc--){
        go();
    }



}
    
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...