이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "overtaking.h"
#include <algorithm>
#include <map>
#include <numeric>
using namespace std;
typedef long long ll;
const int N = 1000 + 3;
ll dp[N][N];
int n, m;
ll t[N], w[N], s[N], l, x;
map<ll, vector<int>> groups[N];
ll time_at_sorting[N][N];
void reorder_buses(){
int new_n = n;
for(int i = 0; i < new_n; ++i){
if(w[i] <= x){
--new_n;
swap(w[i], w[new_n]);
swap(t[i], t[new_n]);
--i;
}
}
n = new_n;
vector<int> perm(n);
iota(perm.begin(), perm.end(), 0);
sort(perm.begin(), perm.end(), [&](int l, int r){
if(w[l] != w[r])
return w[l] < w[r];
return t[l] < t[r];
});
static ll tmp[N];
copy(t, t + n, tmp);
for(int i = 0; i < n; ++i){
t[i] = tmp[perm[i]];
}
copy(w, w + n, tmp);
for(int i = 0; i < n; ++i){
w[i] = tmp[perm[i]];
}
}
void init_groups(){
for(int i = 0; i < n; ++i){
time_at_sorting[0][i] = t[i];
groups[0][t[i]].push_back(i);
}
for(int station = 1; station < m; ++station){
vector<int> order;
for(auto &[time, v]: groups[station - 1]){
for(int x: v){
order.push_back(x);
}
}
for(int i = 0; i < n; ++i){
time_at_sorting[station][i] = time_at_sorting[station - 1][i] + (s[station] - s[station - 1]) * w[i];
}
ll max_so_far = 0;
for(int x: order){
max_so_far = max(max_so_far, time_at_sorting[station][x]);
time_at_sorting[station][x] = max_so_far;
groups[station][max_so_far].push_back(x);
}
for(auto &[time, buses]: groups[station]){
sort(buses.begin(), buses.end());
}
}
}
void init_buses(){
reorder_buses();
init_groups();
}
ll calc_time(int station, ll time){
if(station == m - 1){
return time;
}
auto iter = groups[station].lower_bound(time);
if(iter == groups[station].begin()){
return (s[m - 1] - s[station]) * x + time;
}
--iter;
int bus = iter->second.back();
ll next_time = (s[station + 1] - s[station]) * x + time;
if(next_time > time_at_sorting[station + 1][bus]){
return calc_time(station + 1, next_time);
}
return dp[station + 1][bus];
/*int l = station + 1, r = m;
while(l != r){
int mid = (l + r) >> 1;
ll time_at_mid = (s[mid] - s[station]) * x + time;
if(time_at_sorting[mid][bus] >= time_at_mid){
r = mid;
}
else{
l = mid + 1;
}
}
int next_station = l;
if(next_station == m){
return (s[m - 1] - s[station]) * x + time;
}
return dp[next_station][bus];*/
}
void calc_dp(){
for(int station = m - 1; station >= 0; --station){
if(station == m - 1){
for(int i = 0; i < n; ++i){
dp[station][i] = time_at_sorting[station][i];
}
continue;
}
for(int i = 0; i < n; ++i){
dp[station][i] = calc_time(station, time_at_sorting[station][i]);
}
}
}
void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S)
{
l = L, n = N, x = X, m = M;
copy(T.begin(), T.end(), t);
copy(W.begin(), W.end(), w);
copy(S.begin(), S.end(), s);
init_buses();
calc_dp();
}
ll arrival_time(ll Y)
{
return calc_time(0, Y);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |