제출 #1220951

#제출 시각아이디문제언어결과실행 시간메모리
1220951PotatoMan추월 (IOI23_overtaking)C++17
0 / 100
0 ms328 KiB
#include "overtaking.h" #include <bits/stdc++.h> using namespace std; using ll = long long; struct Bus { ll t, w; int id; }; bool cmp(const Bus &a, const Bus &b) { if (a.t == b.t) return a.w < b.w; return a.t < b.t; } int N, M; vector<int> stations; vector<Bus> buses, buses_init; vector<ll> arrTimes_station[1005]; ll dist(int i) { return stations[i] - stations[i - 1]; } ll compute(ll t, ll w, int j) { return t + dist(j) * w; } void init(int Lp, int Np, vector<ll> Tp, vector<int> Wp, int Xp, int Mp, vector<int> Sp) { buses.clear(); stations = Sp; for (int i = 0; i < Np; i++) { if (Wp[i] >= Xp) buses.push_back({Tp[i], Wp[i], i}); } buses.push_back({0, (ll)Xp, Np}); N = (int)buses.size(); M = Mp; buses_init = buses; for (int j = 1; j < M; j++) { sort(buses.begin(), buses.end(), cmp); ll curMax = 0; arrTimes_station[j].clear(); arrTimes_station[j].reserve(N); for (int i = 0; i < N; i++) { ll expected = compute(buses[i].t, buses[i].w, j); buses[i].t = max(expected, curMax); curMax = max(curMax, buses[i].t); arrTimes_station[j].push_back(buses[i].t); } } } ll arrival_time(ll Y) { buses = buses_init; ll arrival = Y, pace = 0; for (auto &b : buses) { if (b.id == N - 1) { b.t = Y; pace = b.w; break; } } for (int j = 1; j < M; j++) { auto &arr = arrTimes_station[j]; int pos = (int)(upper_bound(arr.begin(), arr.end(), arrival) - arr.begin()); ll block = (pos == 0) ? 0 : arr[pos - 1]; arrival = max(arrival + dist(j) * pace, block); for (auto &b : buses) { if (b.id == N - 1) { b.t = arrival; break; } } } for (auto &b : buses) if (b.id == N - 1) return b.t; return -1; }
#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...