Submission #1235850

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235850		alterio	Overtaking (IOI23_overtaking)	C++20	65 / 100	3596 ms	31808 KiB

overtaking

#include "overtaking.h"
#include <bits/stdc++.h>

using namespace std;

const int mxn = 1010;

#define ll long long
#define all(x) (x).begin(), (x).end()

int L, N, X, M;
ll mxDist[mxn][mxn], Time[mxn][mxn];
vector<ll> T;
vector<int> W, S;

bool csort(pair<ll, int> a, pair<ll, int> b) {
    if (a.first != b.first) return a.first < b.first;
    return W[a.second] < W[b.second];
}

void init(int _L, int _N, vector<ll> _T, vector<int> _W, int _X, int _M, vector<int> _S)
{
    L = _L, N = _N, X = _X, M = _M;
    T = _T, W = _W, S = _S;
    vector<pair<ll, int>> V;
    for (int i = 0; i < N; i++) V.push_back({T[i], i});
    for (int i = 0; i < M - 1; i++) {
        sort(all(V), csort);
        vector<pair<ll, int>> newV;
        ll dist = S[i + 1] - S[i];
        ll MX = 0;
        for (int j = 0; j < N; j++) {
            ll TIME = V[j].first, ind = V[j].second;
            ll newTime = TIME + dist * W[ind];
            if (newTime > MX) MX = newTime;
            newV.push_back({max(newTime, MX), ind});
        }
        for (int j = 0; j < N; j++) {
            Time[i][j] = V[j].first;
            if (j) mxDist[i][j] = mxDist[i][j - 1];
            mxDist[i][j] = max(mxDist[i][j], newV[j].first);
        }
        V = newV;
    }
    // for (int i = 0; i < M; i++) {
    //     for (int j = 0; j < N; j++) {
    //         cout << Time[i][j] << " " << mxDist[i][j] << " ";
    //         cout << endl;
    //     }
    //     cout << endl;
    // }
}

ll arrival_time(ll Y)
{
    for (int i = 0; i < M - 1; i++) {
        ll dist = S[i + 1] - S[i];
        int l = 0, r = N;
        if (Time[i][0] >= Y) {
            Y += dist * X;
            continue;
        }
        while (l + 1 < r) {
            int mid = (l + r) / 2;
            if (Time[i][mid] < Y) l = mid;
            else r = mid;
        }
        Y = max(Y + dist * X, mxDist[i][l]);
    }
    return Y;
}

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