제출 #1281242

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281242		tunademayo	Marathon Race 2 (JOI24_ho_t3)	C++20	24 / 100	75 ms	2940 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (1LL<<62);

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

    int N;
    long long L;
    if (!(cin >> N >> L)) return 0;
    vector<long long> X(N);
    for (int i = 0; i < N; ++i) cin >> X[i];
    // compress positions -> distinct pos with counts
    map<long long,int> mp;
    for (auto x : X) mp[x]++;
    vector<long long> pos;
    vector<int> cnts;
    for (auto &p : mp) { pos.push_back(p.first); cnts.push_back(p.second); }
    int M = (int)pos.size();
    // total balls (should equal N)
    int totalBalls = 0;
    for (int c : cnts) totalBalls += c;

    int Q; cin >> Q;
    // Precompute distances between positions (for speed)
    vector<vector<ll>> dist(M, vector<ll>(M,0));
    for (int i = 0; i < M; ++i) for (int j = 0; j < M; ++j) dist[i][j] = llabs(pos[i]-pos[j]);

    // Precompute ballsTaken for mask quickly (we need sum of cnts in mask)
    int maxMask = 1<<M;
    vector<int> ballsInMask;
    if (M <= 20) {
        ballsInMask.assign(maxMask, 0);
        for (int mask = 1; mask < maxMask; ++mask) {
            int b = __builtin_ctz(mask);
            int prev = mask ^ (1<<b);
            ballsInMask[mask] = ballsInMask[prev] + cnts[b];
        }
    }

    for (int qi = 0; qi < Q; ++qi) {
        long long S, G, Tlim; cin >> S >> G >> Tlim;

        if (M == 0) {
            // no balls: just move from S to G with carrying 0 => cost = |S-G| * 1
            ll need = llabs(S - G) * 1;
            cout << (need <= Tlim ? "Yes\n" : "No\n");
            continue;
        }

        if (M > 20) {
            // Fallback: M too large for exact bitmask DP.
            // We can attempt simple heuristic: try two monotone orders + some defer positions (previous attempts).
            // But since you asked correctness, we inform and exit or print NO as safe default.
            // Better: implement the previous heuristic or ask for constraints. For now, print "WA fallback".
            // (In contest you'd need a different algorithm for large M.)
            // We'll run a simple greedy: go left-first and right-first picking at first encounter (no defers).
            auto simulate_simple = [&](long long Sx, long long Gx, bool leftFirst)-> ll {
                // positions sorted ascending in pos[]
                ll time = 0;
                ll cur = Sx;
                int carrying = 0;
                vector<int> picked(M,0);
                // generate visit order
                vector<int> left_idx, right_idx;
                for (int i = 0; i < M; ++i) (pos[i] <= Sx ? left_idx.push_back(i) : right_idx.push_back(i));
                vector<int> order;
                if (leftFirst) {
                    for (int i = (int)left_idx.size()-1; i >= 0; --i) order.push_back(left_idx[i]);
                    for (int i = 0; i < (int)right_idx.size(); ++i) order.push_back(right_idx[i]);
                } else {
                    for (int i = 0; i < (int)right_idx.size(); ++i) order.push_back(right_idx[i]);
                    for (int i = (int)left_idx.size()-1; i >= 0; --i) order.push_back(left_idx[i]);
                }
                for (int id : order) {
                    ll d = llabs(cur - pos[id]);
                    time += d * ( (ll)carrying + 1 );
                    carrying += cnts[id];
                    time += cnts[id];
                    cur = pos[id];
                }
                time += llabs(cur - Gx) * ( (ll)carrying + 1 );
                return time;
            };
            ll t1 = simulate_simple(S,G,true);
            ll t2 = simulate_simple(S,G,false);
            ll best = min(t1,t2);
            cout << (best <= Tlim ? "Yes\n" : "No\n");
            continue;
        }

        // EXACT bitmask DP
        int full = (1<<M) - 1;
        // dp[mask][i] minimal time finishing at pos[i] with mask collected
        vector<vector<ll>> dp(1<<M, vector<ll>(M, INF));
        // initialize: go from S to each i and pick there
        for (int i = 0; i < M; ++i) {
            int mask = 1<<i;
            ll moveCost = llabs(S - pos[i]) * 1; // carrying 0 => multiplier 1
            dp[mask][i] = moveCost + cnts[i];
        }
        // DP
        for (int mask = 1; mask <= full; ++mask) {
            for (int i = 0; i < M; ++i) {
                if (!(mask & (1<<i))) continue;
                ll cur = dp[mask][i];
                if (cur >= INF) continue;
                int taken = ballsInMask[mask];
                // go to any j not yet in mask
                for (int j = 0; j < M; ++j) if (!(mask & (1<<j))) {
                    int nmask = mask | (1<<j);
                    ll moveCost = dist[i][j] * ( (ll)taken + 1 );
                    ll newCost = cur + moveCost + cnts[j];
                    if (newCost < dp[nmask][j]) dp[nmask][j] = newCost;
                }
            }
        }
        // finalize: after full mask, go to G with carrying = totalBalls
        ll ans = INF;
        for (int i = 0; i < M; ++i) {
            if (dp[full][i] >= INF) continue;
            ll finalMove = llabs(pos[i] - G) * ( (ll)totalBalls + 1 );
            ans = min(ans, dp[full][i] + finalMove);
        }
        cout << (ans <= Tlim ? "Yes\n" : "No\n");
    }

    return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 0 / 28
• Subtask 5: 0 / 10
• Subtask 6: 0 / 19
• Subtask 7: 0 / 19