Submission #1220890

#TimeUsernameProblemLanguageResultExecution timeMemory
1220890PotatoManOvertaking (IOI23_overtaking)C++17
0 / 100
0 ms328 KiB
#include "overtaking.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; struct Bus { ll departureTime; ll pace; ll id; }; bool byDepartureTime(const Bus &b1, const Bus &b2) { if (b1.departureTime == b2.departureTime) return b1.pace < b2.pace; return b1.departureTime < b2.departureTime; } vector<Bus> bus; vector<ll> S; ll N, M; ll computeExpArrival(const Bus& b, int stationIndex) { ll distance = S[stationIndex] - S[stationIndex - 1]; return b.departureTime + distance * b.pace; } void init(int Lp, int Np, vector<ll> Tp, vector<int> Wp, int X, int Mp, vector<int> Sp) { // Load regular bus data for (int i = 0; i < Np; i++) { bus.push_back({Tp[i], Wp[i], i}); } // Load reserve bus (ID = Np) bus.push_back({0, X, Np}); // Load stations S.assign(Sp.begin(), Sp.end()); // Set global values N = bus.size(); // N == Np + 1 M = Mp; } ll arrival_time(ll Y) { // Set reserve bus departure time for (auto &b : bus) { if (b.id == N - 1) b.departureTime = Y; } // Simulate station-by-station for (int j = 1; j < M; j++) { sort(bus.begin(), bus.end(), byDepartureTime); ll curMax = 0; for (int i = 0; i < N; i++) { ll exp = computeExpArrival(bus[i], j); bus[i].departureTime = max(exp, curMax); curMax = max(curMax, bus[i].departureTime); } } // Return final arrival time of the reserve bus ll ret; for (auto &b : bus) { if (b.id == N - 1) ret = b.departureTime; } return ret; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...