| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1076265 | Ignut | 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.
/* Ignut
started: 14.08.2024
now: 26.08.2024
████████████████████████████████████████████████████████████████████
████████████████████████████████ ████████████████████████████████
██████████████████████████████ ██████████████████████████████
██████ ██████████████████ ██████████████████ ██████
██████ ██████████████ ██████████████ ██████
██████ ██ ████████████ ████████████ ██ ██████
██████ ████ ██████████ ██████████ ████ ██████
██████ ████ ██████████ ██████████ ████ ██████
██████ ████ ██████████ ██████████ ██████ ██████
██████ ██████ ██████████ ██████████ ██████ ██████
██████ ██████ ████████ ████████ ██████ ██████
██████ ██████ ██████ ██████ ██████ ██████
██████ ████ ████ ████ ████ ██████
██████ ██████████ ████ ██████████ ██████
██████ ██ ██████ ████████ ██████ ██ ██████
██████ ██████ ████████ ██████ ██████
██████ ██ ██ ██████
██████████████████████ ████ ████ ██████████████████████
████████████████████████ ██ ██ ████████████████████████
██████████████████████████ ██████████████████████████
██████████████████████████████ ██████████████████████████████
████████████████████████████████████████████████████████████████████
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll l;
ll n, m;
vector<ll> w;
vector<ll> t;
ll x;
vector<ll> s;
const ll MAXM = 1111;
const ll MAXN = 1111;
ll tim[MAXM][MAXN];
ll spd[MAXM][MAXN];
ll dp[MAXM][MAXN];
ll sz;
void init(ll L, ll N, vector<ll> T, vector<ll> W, ll X, ll M, vector<ll> S) {
l = L; n = N; m = M; w = W; s = S; x = X; t = T;
// <time, speed>
vector<pair<ll, ll>> vec;
for (ll i = 0; i < N; i ++) if (W[i] > X) vec.push_back({T[i], W[i]});
sort(vec.begin(), vec.end());
sz = vec.size();
for (ll i = 0; i < sz; i ++) tim[0][i] = vec[i].first, spd[0][i] = vec[i].second;
for (ll i = 1; i < M; i ++) {
vector<pair<ll, ll>> nxt;
ll maxTime = 0;
for (auto [tim, spd] : vec) {
maxTime = max(maxTime, tim + 1ll * (S[i] - S[i - 1]) * spd);
nxt.push_back({maxTime, spd});
}
vec = nxt;
sort(vec.begin(), vec.end());
for (ll j = 0; j < sz; j ++) tim[i][j] = vec[j].first, spd[i][j] = vec[j].second;
}
for (ll lvl = M - 1; lvl >= 0; lvl --) {
dp[lvl][0] = tim[lvl][0] + 1ll * (L - s[lvl]) * X;
for (ll i = 1; i < sz; i ++) {
if (tim[lvl][i] == tim[lvl][i - 1]) {
dp[lvl][i] = dp[lvl][i - 1];
continue;
}
ll prev_time = tim[lvl][i - 1] + 1ll * (L - s[lvl]) * spd[lvl][i - 1];
ll my_time = tim[lvl][i] + 1ll * (L - s[lvl]) * X;
if (prev_time <= my_time) {
dp[lvl][i] = my_time;
continue;
}
ll lo = lvl + 1, hi = M - 1;
while (lo < hi) {
ll mid = lo + (hi - lo) / 2;
prev_time = tim[lvl][i - 1] + 1ll * (s[mid] - s[lvl]) * spd[lvl][i - 1];
my_time = tim[lvl][i] + 1ll * (s[mid] - s[lvl]) * X;
if (prev_time >= my_time)
hi = mid;
else
lo = mid + 1;
}
// cout << lvl << ' ' << i << " -> " << lo << ' ' << i - 1 << '\n';
dp[lvl][i] = dp[lo][i - 1];
}
}
// for (ll lvl = 0; lvl < M; lvl ++) {
// for (ll i = 0; i < sz; i ++) {
// cout << dp[lvl][i] << ' ';
// }
// cout << '\n';
// }
}
ll arrival_time(ll Y) {
if (Y <= tim[0][0]) {
return 1ll * l * x + Y;
}
ll maxInd = 0;
for (ll i = 0; i < sz; i ++)
if (tim[0][i] < Y)
maxInd = i;
for (ll lvl = 1; lvl < m; lvl ++) {
ll his_time = tim[lvl][maxInd];
ll my_time = Y + 1ll * s[lvl] * x;
if (his_time >= my_time) {
return dp[lvl][maxInd];
}
}
return 1ll * l * x + Y;
}