Submission #604967

#	Time	Username	Problem	Language	Result	Execution time	Memory
604967		snasibov05	Kangaroo (CEOI16_kangaroo)	C++14	51 / 100	757 ms	137036 KiB

kangaroo

#include <bits/stdc++.h>

using namespace std;

const int mxn = 205;
const int m = 1e9 + 7;
int dp[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;
    memset(dp, -1, sizeof(dp));

    calc(n, cs, cf, 0);
    calc(n, cs, cf, 1);

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

    cout << ans << "\n";

    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 30 / 30
• Subtask 3: 15 / 15
• Subtask 4: 0 / 49