Submission #1327204

#TimeUsernameProblemLanguageResultExecution timeMemory
1327204HaroldVemenoKangaroo (CEOI16_kangaroo)C++20
51 / 100
2097 ms62988 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) {
            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 << 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...