oj.uz

Submission #126975

# Submission time Handle Problem Language Result Execution time Memory
126975 2019-07-08T17:25:45 Z darkkcyan Kangaroo (CEOI16_kangaroo) C++14
0 / 100
 145 ms 171640 KB 
#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, nxt - (cur_cs < nxt), cur_cf - (cur_cs < 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.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 171612 KB Output is correct
2 Incorrect 145 ms 171640 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 171612 KB Output is correct
2 Incorrect 145 ms 171640 KB Output isn't correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 171612 KB Output is correct
2 Incorrect 145 ms 171640 KB Output isn't correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 171612 KB Output is correct
2 Incorrect 145 ms 171640 KB Output isn't correct