Submission #1283193

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283193		abc123	은하철도 (APIO24_train)	C++20	5 / 100	1096 ms	24116 KiB

train

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

const long long INF = 1e15;

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) {
    
    struct Train {
        int start_planet, end_planet, depart_time, arrive_time;
        long long cost;
    };
    
    vector<Train> trains(M);
    for (int i = 0; i < M; ++i) {
        trains[i] = {X[i], Y[i], A[i], B[i], (long long)C[i]};
    }

    int max_time = 1001; // Large enough to cover all possible times
    
    // Find actual max time from train schedules
    for (const auto& train : trains) {
        max_time = max(max_time, train.arrive_time);
    }
    for (int i = 0; i < W; ++i) {
        max_time = max(max_time, R[i]);
    }
    max_time = min(max_time + 1, 1001);

    // DP[planet][time][mask] = min cost to reach this state
    map<tuple<int,int,int>, long long> dp;
    dp[{0, 0, 0}] = 0;
    
    priority_queue<tuple<long long, int, int, int>, 
                   vector<tuple<long long, int, int, int>>,
                   greater<tuple<long long, int, int, int>>> pq;
    pq.push({0, 0, 0, 0}); // cost, planet, time, mask
    
    while (!pq.empty()) {
        auto [cost, planet, time, mask] = pq.top();
        pq.pop();
        
        auto state = make_tuple(planet, time, mask);
        if (dp.count(state) && dp[state] < cost) continue;
        
        // Check if we reached destination with all meals
        if (planet == N - 1 && mask == (1 << W) - 1) {
            return cost;
        }
        
        // Option 1: Take meals on current planet at current time (pay cost)
        for (int meal = 0; meal < W; ++meal) {
            if (((mask >> meal) & 1) == 0 && L[meal] <= time && time <= R[meal]) {
                int new_mask = mask | (1 << meal);
                long long new_cost = cost + T[planet];
                auto new_state = make_tuple(planet, time, new_mask);
                if (!dp.count(new_state) || dp[new_state] > new_cost) {
                    dp[new_state] = new_cost;
                    pq.push({new_cost, planet, time, new_mask});
                }
            }
        }
        
        // Option 2: Take any train leaving from current planet at or after current time
        for (const auto& train : trains) {
            if (train.start_planet == planet && train.depart_time >= time) {
                int new_mask = mask;
                // Mark meals that are fully covered by train interval as free
                for (int meal = 0; meal < W; ++meal) {
                    if (((new_mask >> meal) & 1) == 0) {
                        if (L[meal] >= train.depart_time && R[meal] <= train.arrive_time) {
                            new_mask |= (1 << meal);
                        }
                    }
                }
                long long new_cost = cost + train.cost;
                auto new_state = make_tuple(train.end_planet, train.arrive_time, new_mask);
                if (!dp.count(new_state) || dp[new_state] > new_cost) {
                    dp[new_state] = new_cost;
                    pq.push({new_cost, train.end_planet, train.arrive_time, new_mask});
                }
            }
        }
    }
    
    return -1;
}

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