Submission #126974

#	Time	Username	Problem	Language	Result	Execution time	Memory
126974		darkkcyan	Kangaroo (CEOI16_kangaroo)	C++14	0 / 100	144 ms	171640 KiB

kangaroo

#include <bits/stdc++.h>
using namespace std;
using namespace std::placeholders;

#define llong long long 
#define xx first
#define yy second
#define len(x) ((int)x.size())
#define rep(i,n) for (int i = -1; ++ i < n; )
#define rep1(i,n) for (int i = 0; i ++ < n; )
#define all(x) x.begin(), x.end()
// #define rand __rand
// mt19937 rand(chrono::system_clock::now().time_since_epoch().count());  // or mt19937_64

#define rem ((llong)1e9+7)
#define UP 1
#define DOWN 0
llong sol_51pts(int n, int cs, int cf) {
#define maxn 222
    assert(n < maxn);
    static llong dp[maxn][maxn][maxn][2];

    function<llong(int, int, int, bool)> cal = [&](int cur_n, int cur_cs, int cur_cf, bool dir) -> llong {
        if (dp[cur_n][cur_cs][cur_cf][dir] >= 0)
            return dp[cur_n][cur_cs][cur_cf][dir];
        if (cur_n == 2) return ((dir == DOWN and cur_cs > cur_cf) or (dir == UP and cur_cs < cur_cf));
        llong& ans = dp[cur_n][cur_cs][cur_cf][dir];
        ans = 0;
        int diff = dir == DOWN ? -1 : 1;
        int nxt = cur_cs + diff;
        while (nxt == cur_cf) nxt += diff;
        if (1 <= nxt and nxt <= cur_n) {
            ans += cal(cur_n, nxt, cur_cf, dir);
            ans += cal(cur_n - 1, cur_cs - (nxt < cur_cs), cur_cf - (nxt < cur_cf), !dir);
        }
        // clog << string(n - cur_n, ' ') << cur_n << ' ' << cur_cs << ' ' << cur_cf << ' ' << (dir ? "up" : "down" ) << ' ' << ans << endl;
        return ans %= rem;
    };

    memset(dp, -1, sizeof(dp));
    return (cal(n, cs, cf, UP) + cal(n, cs, cf, DOWN)) % rem;

#undef maxn
}

int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, cs, cf;
    cin >> n >> cs >> cf;
    cout << sol_51pts(n, cs, cf);

    return 0;
}

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