Submission #1283165

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283165		abc123	Train (APIO24_train)	C++20	0 / 100	35 ms	12644 KiB

train

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

struct Train {
    int x, y, a, b, c;
};

struct State {
    int planet, time, meals_mask;
    long long cost;
    bool operator>(const State &other) const {
        return cost > other.cost;
    }
};

long long solve(int N, int M, int W, vector<int> T,
                vector<int> X, vector<int> Y,
                vector<int> A, vector<int> B, vector<int> C,
                vector<int> L, vector<int> R) {
    vector<Train> trains(M);
    for (int i = 0; i < M; i++) {
        trains[i] = {X[i], Y[i], A[i], B[i], C[i]};
    }

    // Meals time intervals and total required meals
    // Precompute all meals and their time windows

    // DP Dijkstra state space:
    // State: (planet, time, meals_mask)
    // meals_mask - bitmask representing which meals have been taken
    // time up to max 10 as problem constraints say times ≤ 10
    //
    // Since constraints are small (N,M,W ≤ 10), this approach is feasible.

    int max_time = 10;
    long long INF = 1e15;

    // cost[planet][time][meals_mask] = minimal cost to be here
    vector<vector<vector<long long>>> cost(N, vector<vector<long long>>(max_time+1, vector<long long>(1 << W, INF)));
    priority_queue<State, vector<State>, greater<State>> pq;

    // Start at planet 0, time 0, no meals taken
    cost[0][0][0] = 0;
    pq.push({0, 0, 0, 0});

    auto meal_allowed_at = [&](int meal_idx, int t) {
        return (t >= L[meal_idx] && t <= R[meal_idx]);
    };

    while (!pq.empty()) {
        State cur = pq.top();
        pq.pop();
        if (cost[cur.planet][cur.time][cur.meals_mask] < cur.cost) continue;

        // If reached planet N-1 with all meals taken
        if (cur.planet == N-1 && cur.meals_mask == (1 << W) - 1) {
            return cur.cost;
        }

        // Option 1: Take meals on the current planet if waiting (pay cost)
        // or eat free on a train (on train means time interval on any train route?)
        // Here, "waiting" means not on train, so if we do not move to next train yet,
        // we pay cost per meal on planet

        // Try taking any meal not yet taken, at current time if allowed
        for (int i = 0; i < W; i++) {
            if (!(cur.meals_mask & (1 << i)) && meal_allowed_at(i, cur.time)) {
                int new_mask = cur.meals_mask | (1 << i);
                // Can eat free on train route that covers this time - to check
                // but here we only store state on planet, meals taken here cost T[cur.planet]
                // So only pay if waiting on planet (no train now)
                long long new_cost = cur.cost + T[cur.planet];
                if (new_cost < cost[cur.planet][cur.time][new_mask]) {
                    cost[cur.planet][cur.time][new_mask] = new_cost;
                    pq.push({cur.planet, cur.time, new_mask, new_cost});
                }
            }
        }

        // Option 2: Take a train starting from current planet at or after current time
        // Transfer time is zero, so we can only board trains where start planet == cur.planet and departure time >= cur.time
        for (int i = 0; i < M; i++) {
            if (trains[i].x == cur.planet && trains[i].a >= cur.time) {
                // On train interval [A[i], B[i]] meals are free (if meal time in this range)
                // So take meals for free on this train on the time interval
                int new_mask = cur.meals_mask;
                for (int m = 0; m < W; m++) {
                    if (!(new_mask & (1 << m))) {
                        // If meal window overlaps train interval, can take free
                        if (!(R[m] < trains[i].a || L[m] > trains[i].b)) {
                            new_mask |= (1 << m);
                        }
                    }
                }
                long long new_cost = cur.cost + trains[i].c;
                if (new_cost < cost[trains[i].y][trains[i].b][new_mask]) {
                    cost[trains[i].y][trains[i].b][new_mask] = new_cost;
                    pq.push({trains[i].y, trains[i].b, new_mask, new_cost});
                }
            }
        }

        // Option 3: Wait time forward if no train (increase time by 1)
        // Only if next time <= max_time
        if (cur.time < max_time) {
            // Waiting means pay per meal if eaten at this new time
            // But we do not know here if any meals taken at new time, so no cost added here except meals when taken
            if (cur.cost < cost[cur.planet][cur.time+1][cur.meals_mask]) {
                cost[cur.planet][cur.time+1][cur.meals_mask] = cur.cost;
                pq.push({cur.planet, cur.time+1, cur.meals_mask, cur.cost});
            }
        }
    }

    // No way to reach planet N-1 with all meals
    return -1;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 60