Submission #1327205

#TimeUsernameProblemLanguageResultExecution timeMemory
1327205HaroldVemenoKangaroo (CEOI16_kangaroo)C++20
51 / 100
2096 ms42888 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;

    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(abs(f - F) > n-i && abs((n-f-1) - F) > n-i) 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);
        // cout << "i " << i << '\n';
        // for(int f = 0; f < i; ++f) {
        //     for(int s = 0; s < i; ++s) {
        //         cout << dp[f][s] << ' ';
        //     }
        //     cout << '\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...