oj.uz

Submission #126983

# Submission time Handle Problem Language Result Execution time Memory
126983 2019-07-08T17:54:43 Z darkkcyan Kangaroo (CEOI16_kangaroo) C++14
51 / 100
 447 ms 344440 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];
    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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 343032 KB Output is correct
2 Correct 294 ms 343068 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 343032 KB Output is correct
2 Correct 294 ms 343068 KB Output is correct
3 Correct 281 ms 342876 KB Output is correct
4 Correct 281 ms 342904 KB Output is correct
5 Correct 283 ms 342980 KB Output is correct
6 Correct 283 ms 343008 KB Output is correct
7 Correct 284 ms 343032 KB Output is correct
8 Correct 283 ms 343112 KB Output is correct
9 Correct 285 ms 343036 KB Output is correct
10 Correct 309 ms 343024 KB Output is correct
11 Correct 284 ms 343164 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 343032 KB Output is correct
2 Correct 294 ms 343068 KB Output is correct
3 Correct 281 ms 342876 KB Output is correct
4 Correct 281 ms 342904 KB Output is correct
5 Correct 283 ms 342980 KB Output is correct
6 Correct 283 ms 343008 KB Output is correct
7 Correct 284 ms 343032 KB Output is correct
8 Correct 283 ms 343112 KB Output is correct
9 Correct 285 ms 343036 KB Output is correct
10 Correct 309 ms 343024 KB Output is correct
11 Correct 284 ms 343164 KB Output is correct
12 Correct 392 ms 344316 KB Output is correct
13 Correct 370 ms 344272 KB Output is correct
14 Correct 337 ms 344348 KB Output is correct
15 Correct 394 ms 344356 KB Output is correct
16 Correct 291 ms 344284 KB Output is correct
17 Correct 400 ms 344284 KB Output is correct
18 Correct 333 ms 344140 KB Output is correct
19 Correct 398 ms 344312 KB Output is correct
20 Correct 447 ms 344440 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 284 ms 343032 KB Output is correct
2 Correct 294 ms 343068 KB Output is correct
3 Correct 281 ms 342876 KB Output is correct
4 Correct 281 ms 342904 KB Output is correct
5 Correct 283 ms 342980 KB Output is correct
6 Correct 283 ms 343008 KB Output is correct
7 Correct 284 ms 343032 KB Output is correct
8 Correct 283 ms 343112 KB Output is correct
9 Correct 285 ms 343036 KB Output is correct
10 Correct 309 ms 343024 KB Output is correct
11 Correct 284 ms 343164 KB Output is correct
12 Correct 392 ms 344316 KB Output is correct
13 Correct 370 ms 344272 KB Output is correct
14 Correct 337 ms 344348 KB Output is correct
15 Correct 394 ms 344356 KB Output is correct
16 Correct 291 ms 344284 KB Output is correct
17 Correct 400 ms 344284 KB Output is correct
18 Correct 333 ms 344140 KB Output is correct
19 Correct 398 ms 344312 KB Output is correct
20 Correct 447 ms 344440 KB Output is correct
21 Runtime error 22 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -