Submission #126983

#	Time	Username	Problem	Language	Result	Execution time	Memory
126983		darkkcyan	Kangaroo (CEOI16_kangaroo)	C++14	51 / 100	447 ms	344440 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];
    static llong pref_sum[maxn][maxn][maxn][2];

    function<llong(int, int, int, bool)> cal_pref_sum, cal;

    cal_pref_sum = [&](int cur_n, int cur_cf, int cur_cs, bool dir) -> llong {
        if (cur_cs == 0) return 0;
        llong& ans = pref_sum[cur_n][cur_cf][cur_cs][dir];
        if (ans == -1) ans = cal_pref_sum(cur_n, cur_cf, cur_cs - 1, dir) + cal(cur_n, cur_cf, cur_cs, dir);
        return ans %= rem;
    };

    cal = [&](int cur_n, int cur_cf, int cur_cs, bool dir) -> llong {
        llong& ans = dp[cur_n][cur_cf][cur_cs][dir];
        if (ans != -1) return ans;
        if (cur_cf == cur_cs) return 0;
        if (cur_n == 2) return ((dir == DOWN and cur_cs > cur_cf) or (dir == UP and cur_cs < cur_cf));
        int start, stop;
        if (dir == DOWN) {
            start = 1;
            stop = cur_cs - 1;
        } else {
            start = cur_cs;
            stop = cur_n - 1;
        }

        int nxt_cf = cur_cf - (cur_cf > cur_cs);
        ans = cal_pref_sum(cur_n - 1, nxt_cf, stop, !dir);
        ans += rem - cal_pref_sum(cur_n - 1, nxt_cf, start - 1, !dir);
        ans %= rem;
        // clog << cur_n << ' ' << cur_cf << ' ' << cur_cs << ' ' << dir << ' ' << ans << endl;
        return ans;
    };

    memset(dp, -1, sizeof(dp));
    memset(pref_sum, -1, sizeof pref_sum);
    return (cal(n, cf, cs, UP) + cal(n, cf, cs, 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: 6 / 6
• Subtask 2: 30 / 30
• Subtask 3: 15 / 15
• Subtask 4: 0 / 49