제출 #1239008

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1239008		trimkus	Collecting Stamps 3 (JOI20_ho_t3)	C++20	25 / 100	2101 ms	135324 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll INF = (ll)1e18;
int N;
ll Lt;
vector<ll> x, t;

// memo[l][r][k][side] = best (minimum) time we've seen so far to reach state (l,r,k,side)
static ll memo[205][205][205][2];

int best_count = 0;

// compute the circular distance on [0, Lt)
inline ll dist(ll A, ll B) {
    ll d = llabs(A - B);
    return min(d, Lt - d);
}

// dfs from state (l, r, k, side), with elapsed time = cur_t and stamps collected = k
// side = 0 means currently at x[l], side = 1 means at x[r]
void dfs(int l, int r, int k, int side, ll cur_t) {
    // update global best
    best_count = max(best_count, k);

    // try to extend interval on the left (i.e. visit l+1)
    if (l + 1 < r) {
        ll next_pos = x[l+1];
        ll here     = (side == 0 ? x[l] : x[r]);
        ll travel   = dist(here, next_pos);
        ll nt       = cur_t + travel;
        int nk      = k + (nt <= t[l+1] ? 1 : 0);
        int nside   = 0;         // now we're at the left end
        int nl = l+1, nr = r;
        if (nt < memo[nl][nr][nk][nside]) {
            memo[nl][nr][nk][nside] = nt;
            dfs(nl, nr, nk, nside, nt);
        }
    }

    // try to extend interval on the right (i.e. visit r-1)
    if (l < r - 1) {
        ll next_pos = x[r-1];
        ll here     = (side == 0 ? x[l] : x[r]);
        ll travel   = dist(here, next_pos);
        ll nt       = cur_t + travel;
        int nk      = k + (nt <= t[r-1] ? 1 : 0);
        int nside   = 1;         // now we're at the right end
        int nl = l, nr = r-1;
        if (nt < memo[nl][nr][nk][nside]) {
            memo[nl][nr][nk][nside] = nt;
            dfs(nl, nr, nk, nside, nt);
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> Lt;
    x.resize(N+2);
    t.resize(N+2);
    for(int i = 1; i <= N; ++i) cin >> x[i];
    // add the “sentinel” stands at 0 and Lt
    x[0]       = 0;
    x[N+1]     = Lt;
    t[0]       = t[N+1] = -INF;  // unreachable, but we never stamp them
    for(int i = 1; i <= N; ++i) cin >> t[i];

    // initialize memo to INF
    for(int i = 0; i < 205; ++i)
    for(int j = 0; j < 205; ++j)
    for(int k = 0; k < 205; ++k)
      memo[i][j][k][0] = memo[i][j][k][1] = INF;

    // start from the “empty” interval [0, N+1], with 0 stamps, at both ends
    memo[0][N+1][0][0] = memo[0][N+1][0][1] = 0;
    dfs(0, N+1, 0, 0, 0);
    dfs(0, N+1, 0, 1, 0);

    cout << best_count << "\n";
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 75