Submission #1076302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076302		Ignut	Overtaking (IOI23_overtaking)	C++17	19 / 100	8 ms	16476 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];
                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;
            }
            int lo = lvl + 1, hi = M - 1;
            while (lo < hi) {
                int 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 (int lvl = 0; lvl < M; lvl ++) {
    //     for (int i = 0; i < sz; i ++) {
    //         cout << dp[lvl][i] << ' ';
    //     }
    //     cout << '\n';
    // }
}

ll arrival_time(ll Y) {
    // ll t = Y;
    // for (int lvl = 0; lvl < m - 1; lvl ++) {
    //     ll nxt = t + 1ll * (s[lvl + 1] - s[lvl]) * x; 
    //     for (int i = 0; i < sz; i ++)   
    //         if (tim[lvl][i] < t)
    //             nxt = max(nxt, nxt_tim[lvl][i]);
    //     t = nxt;
    // }
    // return t;

    if (Y <= tim[0][0]) {
        return 1ll * l * x + Y;
    }
    int maxInd = 0;
    for (int i = 0; i < sz; i ++)
        if (tim[0][i] < Y)
            maxInd = i;
    for (int 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;
}

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