Submission #1102186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102186		chaytheoconchotuongdolaem	Long Distance Coach (JOI17_coach)	C++17	0 / 100	287 ms	262144 KiB

coach

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cstdio>
#include <queue>
#include <climits>

using namespace std;

typedef long long ll;

struct Event {
    ll time;
    int type; // 0: need water, 1: refill
    int id;   // person id if type == 0, refill id if type == 1
    Event(ll t, int tp, int i) : time(t), type(tp), id(i) {}
    bool operator<(const Event& other) const {
        if (time != other.time)
            return time > other.time; // min-heap
        return type > other.type;     // process water needs before refills
    }
};

struct Person {
    ll first_need;
    ll refund_cost;
    vector<ll> need_times;
};

int main() {
    // Read input
    ll X, N, M, W, T;
    cin >> X >> N >> M >> W >> T;
    
    vector<ll> refill_times;
    refill_times.push_back(0); // can refill before departure
    for (int i = 0; i < N; ++i) {
        ll Si;
        cin >> Si;
        refill_times.push_back(Si);
    }
    sort(refill_times.begin(), refill_times.end());
    refill_times.push_back(X); // Arrival at city O

    vector<Person> passengers(M);
    for (int j = 0; j < M; ++j) {
        ll Dj, Cj;
        cin >> Dj >> Cj;
        passengers[j].first_need = Dj;
        passengers[j].refund_cost = Cj;
        // Generate all need times for the passenger before arrival
        for (ll t = Dj; t < X; t += T) {
            passengers[j].need_times.push_back(t);
        }
    }

    // Driver's need times
    vector<ll> driver_need_times;
    for (ll t = 0; t < X; t += T) {
        driver_need_times.push_back(t);
    }

    // All events
    priority_queue<Event> events;
    // Add refill events
    for (int i = 1; i < refill_times.size() - 1; ++i) { // exclude 0 and X
        events.emplace(refill_times[i], 1, i);
    }
    // Add water need events
    int passenger_count = passengers.size();
    for (int j = 0; j < passenger_count; ++j) {
        for (ll t : passengers[j].need_times) {
            events.emplace(t, 0, j);
        }
    }
    for (ll t : driver_need_times) {
        events.emplace(t, 0, M); // Use M as driver's id
    }

    // Since no two people need water at the same time, we can proceed sequentially
    ll total_cost = 0;
    ll water_left = 0;
    int next_refill_index = 1; // Index in refill_times
    ll current_time = 0;
    set<int> onboard_passengers;
    for (int j = 0; j < M; ++j) {
        onboard_passengers.insert(j);
    }
    // Must ensure the driver stays onboard
    bool driver_onboard = true;

    // For this simplified implementation, we will keep water in the machine throughout the trip
    // because we cannot avoid the driver needing water
    // So total water needed is total times driver needs water + total times passengers need water
    // Let's compute total water needs
    ll total_water_needs = driver_need_times.size(); // Driver's water needs
    for (int j = 0; j < M; ++j) {
        total_water_needs += passengers[j].need_times.size();
    }

    // Compute total water cost
    ll total_water_cost = total_water_needs * W;

    // Compute refund costs for each passenger
    vector<ll> refund_costs(M);
    for (int j = 0; j < M; ++j) {
        refund_costs[j] = passengers[j].refund_cost;
    }

    // Since we cannot avoid providing water to any passenger, total refund cost is zero
    ll total_refund_cost = 0;

    // Total cost is total_water_cost + total_refund_cost
    total_cost = total_water_cost + total_refund_cost;

    // Output the total cost
    cout << total_cost << endl;

    return 0;
}

Compilation message (stderr)

coach.cpp: In function 'int main()':
coach.cpp:68:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for (int i = 1; i < refill_times.size() - 1; ++i) { // exclude 0 and X
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~~~
coach.cpp:84:8: warning: unused variable 'water_left' [-Wunused-variable]
   84 |     ll water_left = 0;
      |        ^~~~~~~~~~
coach.cpp:85:9: warning: unused variable 'next_refill_index' [-Wunused-variable]
   85 |     int next_refill_index = 1; // Index in refill_times
      |         ^~~~~~~~~~~~~~~~~
coach.cpp:86:8: warning: unused variable 'current_time' [-Wunused-variable]
   86 |     ll current_time = 0;
      |        ^~~~~~~~~~~~
coach.cpp:92:10: warning: unused variable 'driver_onboard' [-Wunused-variable]
   92 |     bool driver_onboard = true;
      |          ^~~~~~~~~~~~~~

• Subtask 1: 0 / 16
• Subtask 2: 0 / 30
• Subtask 3: 0 / 25
• Subtask 4: 0 / 29