제출 #855924

#제출 시각아이디문제언어결과실행 시간메모리
855924Sorting추월 (IOI23_overtaking)C++17
19 / 100
3 ms15452 KiB
#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){ 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(); 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 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...