Submission #1076368

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076368		Ignut	Overtaking (IOI23_overtaking)	C++17	100 / 100	452 ms	73688 KiB

overtaking

/* Ignut
started: 14.08.2024
now: 26.08.2024
████████████████████████████████████████████████████████████████████
████████████████████████████████    ████████████████████████████████
██████████████████████████████        ██████████████████████████████
██████      ██████████████████        ██████████████████      ██████
██████          ██████████████        ██████████████          ██████
██████      ██    ████████████        ████████████    ██      ██████
██████      ████    ██████████        ██████████    ████      ██████
██████      ████      ██████████    ██████████      ████      ██████
██████      ████      ██████████    ██████████    ██████      ██████
██████      ██████    ██████████    ██████████    ██████      ██████
██████      ██████    ████████        ████████    ██████      ██████
██████      ██████      ██████        ██████      ██████      ██████
██████      ████        ████            ████        ████      ██████
██████            ██████████    ████    ██████████            ██████
██████      ██      ██████    ████████    ██████      ██      ██████
██████      ██████            ████████            ██████      ██████
██████                    ██            ██                    ██████
██████████████████████      ████    ████      ██████████████████████
████████████████████████      ██    ██      ████████████████████████
██████████████████████████                ██████████████████████████
██████████████████████████████        ██████████████████████████████
████████████████████████████████████████████████████████████████████
*/
 
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;

int l;
int n, m;
vector<int> w;
vector<ll> t;
int x;
vector<int> s;

const int MAXM = 1111;
const int MAXN = 1111;

ll tim[MAXM][MAXN];
ll nxt_tim[MAXN][MAXN];
ll spd[MAXM][MAXN];

ll dp[MAXM][MAXN];

int sz;

void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S) {
    l = L; n = N; m = M; w = W; s = S; x = X; t = T;

    // <time, speed>
    vector<pair<ll, ll>> vec;
    for (int 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 (int i = 0; i < sz; i ++) tim[0][i] = vec[i].first, spd[0][i] = vec[i].second;

    for (int i = 1; i < M; i ++) {
        vector<pair<ll, ll>> nxt;
        ll maxTime = 0;
        for (int j = 0; j < sz; j ++) {
            auto [tim, spd] = vec[j];
            maxTime = max(maxTime, tim + 1ll * (S[i] - S[i - 1]) * spd);
            nxt.push_back({maxTime, spd});
            nxt_tim[i - 1][j] = maxTime;
        }
        vec = nxt;
        sort(vec.begin(), vec.end());
        for (int j = 0; j < sz; j ++) tim[i][j] = vec[j].first, spd[i][j] = vec[j].second;
    }


    for (int lvl = M - 1; lvl >= 0; lvl --) {
        dp[lvl][0] = tim[lvl][0] + 1ll * (L - s[lvl]) * X;
        for (int i = 1; i < sz; i ++) {
            if (tim[lvl][i] == tim[lvl][i - 1]) {
                dp[lvl][i] = dp[lvl][i - 1];
                // cout << "continue for " << lvl << ' ' << i << '\n';
                continue;
            }
            ll prev_time = tim[M - 1][i - 1];
            ll my_time = tim[lvl][i] + 1ll * (L - s[lvl]) * X;
            // cout << "prev_time vs my_time :: " << prev_time << " vs " << my_time << '\n';
            if (prev_time <= my_time) {
                dp[lvl][i] = my_time;
                continue;
            }
            // if (lvl == 1 && i == 2) cout << "+\n";
            int lo = lvl + 1, hi = M - 1;
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;
                prev_time = tim[mid][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];
        }
    }
}

ll arrival_time(ll Y) {
    if (Y <= tim[0][0]) {
        return 1ll * l * x + Y;
    }
    int lo = 0, hi = sz - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;
        if (tim[0][mid] < Y)
            lo = mid;
        else
            hi = mid - 1;
    }
    int maxInd = lo;
    
    if (tim[m - 1][maxInd] < Y + 1ll * s[m - 1] * x)
        return 1ll * l * x + Y;

    lo = 0, hi = m - 1;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (tim[mid][maxInd] >= Y + 1ll * s[mid] * x)
            hi = mid;
        else
            lo = mid + 1;
    }
    return dp[lo][maxInd];
}

• Subtask 0: 0 / 0
• Subtask 1: 9 / 9
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 26 / 26
• Subtask 5: 35 / 35