Submission #604979

#TimeUsernameProblemLanguageResultExecution timeMemory
604979snasibov05Kangaroo (CEOI16_kangaroo)C++14
51 / 100
174 ms208760 KiB
#include <bits/stdc++.h>

using namespace std;

const int mxn = 205;
const int m = 1e9 + 7;
int dp[mxn][mxn][mxn][2];
int pref[mxn][mxn][mxn][2];
int suf[mxn][mxn][mxn][2];
// dir : 0 -> left, 1 -> right;

void calc(int sz, int st, int fn, int dir){
    if (dp[sz][st][fn][dir] != -1) return;
    if (st == fn) {
        if (sz == 1) dp[sz][st][fn][dir] = 1;
        else dp[sz][st][fn][dir] = 0;
        return;
    }

    dp[sz][st][fn][dir] = 0;
    if (dir == 0){
        for (int to = 1; to < st; ++to){
            if (st < fn) {
                calc(sz - 1, to, fn - 1, 1);
                dp[sz][st][fn][dir] += dp[sz - 1][to][fn - 1][1];
                dp[sz][st][fn][dir] %= m;
            }
            else {
                calc(sz - 1, to, fn, 1);
                dp[sz][st][fn][dir] += dp[sz - 1][to][fn][1];
                dp[sz][st][fn][dir] %= m;
            }
        }
    } else{
        for (int to = st+1; to <= sz; ++to){
            if (st < fn) {
                calc(sz - 1, to - 1, fn - 1, 0);
                dp[sz][st][fn][dir] += dp[sz - 1][to - 1][fn - 1][0];
                dp[sz][st][fn][dir] %= m;
            }
            else {
                calc(sz - 1, to - 1, fn, 0);
                dp[sz][st][fn][dir] += dp[sz - 1][to - 1][fn][0];
                dp[sz][st][fn][dir] %= m;
            }
        }
    }
}

int main() {
    int n, cs, cf; cin >> n >> cs >> cf;

    dp[1][1][1][0] = dp[1][1][1][1] = 1;
    pref[1][1][1][0] = pref[1][1][1][1] = 1;
    suf[1][1][1][0] = suf[1][1][1][1] = 1;
    for (int sz = 2; sz <= n; ++sz){
        for (int fn = 1; fn <= sz; ++fn){
            for (int st = 1; st <= sz; ++st){
                if (st == fn) continue;
                if (st < fn) {
                    dp[sz][st][fn][0] += pref[sz - 1][st - 1][fn - 1][1];
                    dp[sz][st][fn][0] %= m;
                } else{
                    dp[sz][st][fn][0] += pref[sz - 1][st - 1][fn][1];
                    dp[sz][st][fn][0] %= m;
                }

                if (st < fn) {
                    dp[sz][st][fn][1] += suf[sz - 1][st][fn - 1][0];
                    dp[sz][st][fn][1] %= m;
                } else{
                    dp[sz][st][fn][1] += suf[sz - 1][st][fn][0];
                    dp[sz][st][fn][1] %= m;
                }
            }

            for (int st = 1; st <= sz; ++st) pref[sz][st][fn][1] = (pref[sz][st-1][fn][1] + dp[sz][st][fn][1]) % m;
            for (int st = sz; st > 0; --st) suf[sz][st][fn][0] = (suf[sz][st+1][fn][0] + dp[sz][st][fn][0]) % m;
        }
    }

    int ans = dp[n][cs][cf][0] + dp[n][cs][cf][1];
    ans %= m;

    cout << ans << "\n";

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...