Submission #127511

#	Time	Username	Problem	Language	Result	Execution time	Memory
127511		darkkcyan	Kangaroo (CEOI16_kangaroo)	C++14	100 / 100	38 ms	32376 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

namespace solution_51_points {
    // the solution is similar to the official solution, but I don't swap cs and cf.
    // I check them by hand and decrease cf if necessary.
    const int maxn = 222;
    llong dp[maxn][maxn][maxn][2];  // dp[n][cs][cf][dir]
                                    //   n - the number of cells in the garden.
                                    //   cs - the starting cell
                                    //   cf - the final cell
                                    //   dir - the current direction to move (UP or DOWN)
    llong pref_sum[maxn][maxn][maxn][2];
    // pref_sum[n][cs][cf][dir] = dp[n][1][cf][dir] + dp[n][2][cf][dir] + ... + dp[n][cs][cf][dir]
    // in other words: pref_sum[n][cs][cf][dir] = sum of dp[n][1..cs][cf][dir]

    // these 2 functions lazily calculate pref_sum and dp respectively.
    llong cal_pref_sum(int, int, int, bool);
    llong cal(int, int, int, bool);

    llong cal_pref_sum(int n, int cs, int cf, bool dir) {
        if (cs == 0) return 0;
        llong& ans = pref_sum[n][cs][cf][dir];
        if (ans == -1) ans = cal_pref_sum(n, cs - 1, cf, dir) + cal(n, cs, cf, dir);
        return ans %= rem;
    }

    llong cal(int n, int cs, int cf, bool dir) {
        llong& ans = dp[n][cs][cf][dir];
        if (ans != -1) return ans;
        if (cf == cs) return 0;
        if (n == 2) return ((dir == DOWN and cs > cf) or (dir == UP and cs < cf));
        int range_begin, range_end;
        if (dir == DOWN) {
            range_begin = 1;
            range_end = cs - 1;
        } else {
            range_begin = cs;
            range_end = n - 1;
        }

        int nxt_cf = cf - (cf > cs);
        ans = cal_pref_sum(n - 1, range_end, nxt_cf, !dir);
        ans += rem - cal_pref_sum(n - 1, range_begin - 1, nxt_cf, !dir);
        ans %= rem;
        // clog << n << ' ' << cs << ' ' << cf << ' ' << dir << ' ' << ans << endl;
        return ans;
    }

    llong solve(int n, int cs, int cf) {
        memset(dp, -1, sizeof(dp));
        memset(pref_sum, -1, sizeof pref_sum);
        return (cal(n, cf, cs, UP) + cal(n, cf, cs, DOWN)) % rem;
    }
};

namespace solution_100_points {
    const int maxn = 2020;
    llong dp[maxn][maxn];

    llong solve(int n, int cs, int cf) {
        memset(dp, 0, sizeof dp);
        dp[0][0] = 1;
        rep1(i, n) {
            if (i == cs or i == cf) {
                rep1(f, i) {
                    (dp[i][f] += dp[i - 1][f] + dp[i - 1][f - 1]) %= rem;
                }
            } else {
                int unfilled_endpoints = int(i < cs) + int(i < cf);
                //clog << i << ' ' << unfilled_endpoints << endl;
                rep1(f, i) {
                    (dp[i][f] += dp[i - 1][f + 1] * f) %= rem;
                    // (dp[i][f] += dp[i - 1][f] * (2 * f + unfilled_endpoints - 2)) %= rem;

                    int places_for_new_comp = 1;
                    if (f > 1) places_for_new_comp = f - 2 + unfilled_endpoints;
                    (dp[i][f] += dp[i - 1][f - 1] * places_for_new_comp) %= rem;
                    //clog << "place for comp" << ' ' << i << ' ' << f << ' ' << places_for_new_comp << ' ' << 2 * f + unfilled_endpoints - 2<< endl;
                }
            }

            //rep(f, i + 1) clog << i << ' ' << f << ' ' << dp[i][f] << endl;
        }

        return dp[n][1];
    }
};

int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // using namespace solution_51_points;
    using namespace solution_100_points;

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

    return 0;
}

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