#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
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;
| ^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
287 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
287 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
287 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
287 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
