| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 848508 | mohammedMonem | 추월 (IOI23_overtaking) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "overtaking.h"
#define ll long long
using namespace std;
class bus {
public:
int id;
ll speed, arrivalTime;
explicit bus(int idP = 0, ll speedP = 0, ll arrivalTimeP = 0) {
id = idP, speed = speedP, arrivalTime = arrivalTimeP;
}
friend bool operator<(bus bus1, bus bus2) {
if (bus1.arrivalTime == bus2.arrivalTime) {
return bus1.speed < bus2.speed;
}
return bus1.arrivalTime < bus2.arrivalTime;
}
};
ll reserveBusSpeed;
vector<vector<ll>> trueArrivalTime;//for i bus and j station
vector<ll> sortingStations;
void init(int L, int N, vector<ll> T, vector<ll> W, int X, int M, vector<ll> S) {
trueArrivalTime.resize(N, vector<ll>(M));
for (int i = 0; i < N; ++i) {
trueArrivalTime[i][0] = T[i];
}
reserveBusSpeed = X, sortingStations = S;
vector<ll> expectedArrivalTime(N);//for i bus and j station
vector<bus> sortedBuses(N);
for (int j = 1; j < M; ++j) {
for (int i = 0; i < N; ++i) {
sortedBuses[i] = bus(i, W[i], trueArrivalTime[i][j - 1]);
expectedArrivalTime[i] = trueArrivalTime[i][j - 1] + W[i] * (S[j] - S[j - 1]);
}
ll movingBusesArrivalTime = 0;
sort(sortedBuses.begin(), sortedBuses.end());
for (const auto &i: sortedBuses) {
movingBusesArrivalTime = trueArrivalTime[i.id][j] =
max(movingBusesArrivalTime, expectedArrivalTime[i.id]);
}
}
}
long long arrival_time(long long Y) {
ll prevStationDepartingTime = Y;
for (int j = 1; j < (int) sortingStations.size(); ++j) {
ll reserveBusArrivalTime = prevStationDepartingTime
+ reserveBusSpeed * (sortingStations[j] - sortingStations[j - 1]);
for (const auto &i: trueArrivalTime) {
if (i[j - 1] < prevStationDepartingTime) {
reserveBusArrivalTime = max(reserveBusArrivalTime, i[j]);
}
}
prevStationDepartingTime = reserveBusArrivalTime;
}
return prevStationDepartingTime;
}