Submission #1327700

#TimeUsernameProblemLanguageResultExecution timeMemory
1327700HaroldVemenoKangaroo (CEOI16_kangaroo)C++20
6 / 100
1 ms568 KiB
#include <bits/stdc++.h>

#ifdef GUDEB
    #define D(x) cerr << #x << ": " << (x) << '\n';
    #define ifdeb if(true)
#else
    #define D(x) ;
    #define ifdeb if(false)
#endif

#define all(x) begin(x), end(x)

using namespace std;
using ull = unsigned long long;
using ll = long long;
// #define int ll;

constexpr ll mod = 1000000007;

ll dp1[2002][2002];
ll dp2[2002][2002];

void solve() {
    int n, S, F;
    cin >> n >> S >> F;
    --S; --F;

    ll (*dp)[2002] = dp1;
    ll (*ndp)[2002] = dp2;

    if(F >= n/2) {
        F = n-F-1;
        S = n-S-1;
    }

    dp[F][S] = 1;
    dp[n-F-1][n-S-1] = 1;
    for(int i = n-1; i >= 1; --i) {
        for(int f = 0; f < i; ++f) {
            if(f-1 > F && f+1 < i-F) continue;
            if(f < F-(n-1-i) || f > n-1-F) continue;
            ll d = 0;
            for(int s = 0; s <= f; ++s) {
                d += dp[f+1][s];
                d %= mod;
                ndp[i-1-f][i-1-s] = d;
            }
            for(int s = f+1; s < i; ++s) {
                d += dp[f][s];
                d %= mod;
                ndp[i-1-f][i-1-s] = d;
            }
        }
        swap(dp, ndp);
        // cerr << "i " << i << '\n';
        // for(int f = 0; f < i; ++f) {
        //     for(int s = 0; s < i; ++s) {
        //         cerr << dp[f][s] << ' ';
        //     }
        //     cerr << '\n';
        // }
    }
    cout << dp[0][0] << '\n';


}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << setprecision(20);

    solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...