제출 #127387

#제출 시각아이디문제언어결과실행 시간메모리
127387darkkcyan캥거루 (CEOI16_kangaroo)C++14
51 / 100
1601 ms524288 KiB
#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]
    // or 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;
    }
};

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

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

    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...