제출 #847221

#제출 시각아이디문제언어결과실행 시간메모리
847221I_love_Hoang_Yen추월 (IOI23_overtaking)C++17
65 / 100
3553 ms63312 KiB
#include "overtaking.h" #include <bits/stdc++.h> using namespace std; using ll = long long; constexpr int MAX_SS = 1011; // lines[i]: stores lines between i-th and (i+1)-th sorting stations // each line is represented by its 2 endpoints set<pair<ll, ll>> lines[MAX_SS]; int M; ll X; vector<ll> S; void init( int L, int nBus, vector<ll> T, vector<int> W, int _X, int _M, vector<int> _S) { M = _M; X = _X; S = vector<ll> (_S.begin(), _S.end()); // sort buses in decreasing order of W (so slowest buses are processed first) vector<pair<ll, ll>> buses(nBus); for (int i = 0; i < nBus; ++i) buses[i] = make_pair(W[i], T[i]); std::sort(buses.begin(), buses.end()); std::reverse(buses.begin(), buses.end()); // init gaps between 2 sorting stations for (int i = 0; i < M-1; ++i) { // only M-1 gaps lines[i].clear(); lines[i].insert({0, 0}); } // for each bus, add its line to all gaps for (const auto& [w, t] : buses) { ll cur_time = t; for (int j = 0; j < M-1; ++j) { auto it = std::prev(lines[j].lower_bound({cur_time, 0})); ll exit_time = std::max(it->second, cur_time + w*(S[j+1] - S[j])); lines[j].insert({cur_time, exit_time}); cur_time = exit_time; } } } ll arrival_time(ll Y) { ll cur_time = Y; for (int j = 0; j < M-1; ++j) { auto it = std::prev(lines[j].lower_bound({cur_time, 0})); cur_time = std::max(it->second, cur_time + X*(S[j+1] - S[j])); } return cur_time; }
#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...