Submission #1283192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283192		abc123	은하철도 (APIO24_train)	C++20	Compilation error	0 ms	0 KiB

train

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

const long long INF = 1e15;

struct Train {
    int start_planet, end_planet, depart_time, arrive_time;
    long long cost;
};

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

    int N, M, W;
    cin >> N >> M >> W;

    vector<int> T(N);
    for (int i = 0; i < N; ++i) cin >> T[i];

    vector<Train> trains(M);
    for (int i = 0; i < M; ++i) {
        cin >> trains[i].start_planet >> trains[i].end_planet
            >> trains[i].depart_time >> trains[i].arrive_time >> trains[i].cost;
    }

    vector<int> L(W), R(W);
    for (int i = 0; i < W; ++i) cin >> L[i] >> R[i];

    int max_time = 10; // per problem statement

    // DP[planet][time][mask] = min cost to be here after handling mask meals
    vector<vector<vector<long long>>> dp(N, vector<vector<long long>>(max_time + 1, vector<long long>(1 << W, INF)));
    dp[0][0][0] = 0;

    for (int time = 0; time <= max_time; ++time) {
        for (int planet = 0; planet < N; ++planet) {
            for (int mask = 0; mask < (1 << W); ++mask) {
                if (dp[planet][time][mask] == INF) continue;

                long long base_cost = dp[planet][time][mask];

                // Option 1: Take meals on 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 cost_meal = base_cost + T[planet];
                        if (cost_meal < dp[planet][time][new_mask]) {
                            dp[planet][time][new_mask] = cost_meal;
                        }
                    }
                }

                // Option 2: Wait until next time on same planet without taking meal
                if (time < max_time && base_cost < dp[planet][time + 1][mask]) {
                    dp[planet][time + 1][mask] = base_cost;
                }

                // Option 3: Take any train leaving from planet at or after current time
                for (auto &train : trains) {
                    if (train.start_planet == planet && train.depart_time >= time) {
                        int covered_meals_mask = mask;
                        // Meals fully inside train time interval are free
                        for (int meal = 0; meal < W; ++meal) {
                            if (((covered_meals_mask >> meal) & 1) == 0) {
                                if (L[meal] >= train.depart_time && R[meal] <= train.arrive_time) {
                                    covered_meals_mask |= (1 << meal);
                                }
                            }
                        }
                        long long new_cost = base_cost + train.cost;
                        int arrivaltime = train.arrive_time;
                        int endplanet = train.end_planet;
                        if (new_cost < dp[endplanet][arrivaltime][covered_meals_mask]) {
                            dp[endplanet][arrivaltime][covered_meals_mask] = new_cost;
                        }
                    }
                }
            }
        }
    }

    long long answer = INF;
    for (int time = 0; time <= max_time; ++time) {
        answer = min(answer, dp[N - 1][time][(1 << W) - 1]);
    }

    if (answer == INF) cout << -1 << "\n";
    else cout << answer << "\n";

    return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccYVzM4I.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccAp02bj.o:train.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccYVzM4I.o: in function `main':
grader.cpp:(.text.startup+0x5ce): undefined reference to `solve(int, int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status