| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 990919 | alex_2008 | Overtaking (IOI23_overtaking) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "overtaking.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
typedef long long ll;
vector<vector <pair<ll, ll>>> dp;
vector<vector <ll>> esim;
vector <ll> t;
vector <ll> w, s;
ll n;
ll x;
ll l;
ll m;
bool cmp(pair<ll, ll> x, pair<ll, ll> y) {
if (x.first != y.first) return x.first < y.first;
if (w[x.second] != w[y.second]) return w[x.second] < w[y.second];
return x.second < y.second;
}
void init(ll L, ll N, vector<ll> T, vector<ll> W, ll X, ll M, vector<ll> S) {
//dp[i][j] = [1, i] avtoneri simulyaciayi jamanak (j-rd) stanciayum hertakanutyun
m = M;
l = L;
x = X;
s = S;
dp.clear();
for (ll i = 0; i < N; i++) {
if (W[i] > x) {
//cout << "? " << T[i] << " " << W[i] << "\n";
t.push_back(T[i]);
w.push_back(W[i]);
n++;
}
}
dp.resize(m);
esim.resize(m);
for (ll i = 0; i < n; i++) {
dp[0].push_back({ t[i], i });
}
sort(dp[0].begin(), dp[0].end(), cmp);
for (ll j = 1; j < m; j++) {
ll cur_mx = 0;
for (auto& it : dp[j - 1]) {
cur_mx = max(cur_mx, it.first + w[it.second] * 1ll * (s[j] - s[j - 1]));
dp[j].push_back({ cur_mx, it.second });
}
sort(dp[j].begin(), dp[j].end(), cmp);
map <ll, ll> mp;
for (auto& it : dp[j]) {
mp[it.second] = it.first;
}
cur_mx = 0;
for (auto& it : dp[j - 1]) {
cur_mx = max(cur_mx, mp[it.second]);
esim[j].push_back(cur_mx);
}
}
}
ll arrival_time(ll Y) {
ll cur_ind = 0;
for (auto it : t) {
if (it < Y) cur_ind++;
}
if (cur_ind == 0) {
return l * 1ll * x;
}
ll time = Y;
for (ll i = 1; i < m; i++) {
time = max(time + (s[i] - s[i - 1]) * 1ll * x, esim[i][cur_ind - 1]);
while (cur_ind > 0 && dp[i][cur_ind - 1].first == time) {
cur_ind--;
}
if (cur_ind == 0) {
return (l - s[i]) * 1ll * x + time;
}
}
return time;
}