oj.uz

Submission #126963

# Submission time Handle Problem Language Result Execution time Memory
126963 2019-07-08T17:09:59 Z darkkcyan Kangaroo (CEOI16_kangaroo) C++14
0 / 100
 148 ms 171744 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;
        if (dir == DOWN and cur_cs > 1) {
            ans += cal(cur_n, cur_cs - 1, cur_cf, dir);
            if (cur_cs - 1 != cur_cf) {
                ans += cal(cur_n - 1, cur_cs - 1, cur_cf - (cur_cf > cur_cs), !dir);
            }
        }
        if (dir == UP and cur_cs != cur_n) {
            ans += cal(cur_n, cur_cs + 1, cur_cf, dir);
            if (cur_cs + 1 != cur_cf) {
                ans += cal(cur_n - 1, cur_cs, cur_cf - (cur_cf > cur_cs), !dir);
            }
        }
        // clog << 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 148 ms 171644 KB Output is correct
2 Incorrect 146 ms 171744 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 171644 KB Output is correct
2 Incorrect 146 ms 171744 KB Output isn't correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 171644 KB Output is correct
2 Incorrect 146 ms 171744 KB Output isn't correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 171644 KB Output is correct
2 Incorrect 146 ms 171744 KB Output isn't correct