oj.uz

답안 #127387

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
127387 2019-07-09T10:10:14 Z darkkcyan 캥거루 (CEOI16_kangaroo) C++14
51 / 100
 1601 ms 524288 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

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;
}

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1154 ms 342956 KB Output is correct
2 Correct 318 ms 342956 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1154 ms 342956 KB Output is correct
2 Correct 318 ms 342956 KB Output is correct
3 Correct 356 ms 343076 KB Output is correct
4 Correct 324 ms 342992 KB Output is correct
5 Correct 293 ms 343020 KB Output is correct
6 Correct 284 ms 343088 KB Output is correct
7 Correct 334 ms 342876 KB Output is correct
8 Correct 282 ms 342904 KB Output is correct
9 Correct 287 ms 343092 KB Output is correct
10 Correct 316 ms 343004 KB Output is correct
11 Correct 284 ms 342876 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1154 ms 342956 KB Output is correct
2 Correct 318 ms 342956 KB Output is correct
3 Correct 356 ms 343076 KB Output is correct
4 Correct 324 ms 342992 KB Output is correct
5 Correct 293 ms 343020 KB Output is correct
6 Correct 284 ms 343088 KB Output is correct
7 Correct 334 ms 342876 KB Output is correct
8 Correct 282 ms 342904 KB Output is correct
9 Correct 287 ms 343092 KB Output is correct
10 Correct 316 ms 343004 KB Output is correct
11 Correct 284 ms 342876 KB Output is correct
12 Correct 483 ms 343668 KB Output is correct
13 Correct 301 ms 343596 KB Output is correct
14 Correct 293 ms 343752 KB Output is correct
15 Correct 425 ms 343776 KB Output is correct
16 Correct 510 ms 343748 KB Output is correct
17 Correct 477 ms 343816 KB Output is correct
18 Correct 387 ms 343544 KB Output is correct
19 Correct 476 ms 343748 KB Output is correct
20 Correct 420 ms 343672 KB Output is correct

Subtask #4
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1154 ms 342956 KB Output is correct
2 Correct 318 ms 342956 KB Output is correct
3 Correct 356 ms 343076 KB Output is correct
4 Correct 324 ms 342992 KB Output is correct
5 Correct 293 ms 343020 KB Output is correct
6 Correct 284 ms 343088 KB Output is correct
7 Correct 334 ms 342876 KB Output is correct
8 Correct 282 ms 342904 KB Output is correct
9 Correct 287 ms 343092 KB Output is correct
10 Correct 316 ms 343004 KB Output is correct
11 Correct 284 ms 342876 KB Output is correct
12 Correct 483 ms 343668 KB Output is correct
13 Correct 301 ms 343596 KB Output is correct
14 Correct 293 ms 343752 KB Output is correct
15 Correct 425 ms 343776 KB Output is correct
16 Correct 510 ms 343748 KB Output is correct
17 Correct 477 ms 343816 KB Output is correct
18 Correct 387 ms 343544 KB Output is correct
19 Correct 476 ms 343748 KB Output is correct
20 Correct 420 ms 343672 KB Output is correct
21 Runtime error 1601 ms 524288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -