Submission #1182415

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182415		Lithanium	Overtaking (IOI23_overtaking)	C++20	65 / 100	3595 ms	25924 KiB

overtaking

#pragma GCC optimize("O3")

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

vector<pair<ll, int>> loc[1000];
ll dp[1000][1000]; // time train j arrives at i+1
vector<ll> T;
vector<int> W, S;
int X, L, N, M;

void init(int l, int n, std::vector<long long> t, std::vector<int> w, int x, int m, std::vector<int> s) {
    X = x, L = l, N = n, M = m;
    T = t, W = w, S = s;
    for (int i = 0; i < N; i ++) {
        loc[0].push_back({T[i], i});
    }
    for (int i = 0; i < M-1; i ++) {
        sort(loc[i].begin(), loc[i].end(), [&](const pair<ll, int> a, const pair<ll, int> b) {
            if (a.first != b.first) return a.first < b.first;
            return W[a.second] < W[b.second];
        });
        ll worst = 0;
        for (auto [a, b]:loc[i]) {
            worst = max(worst, (ll)W[b]*(S[i+1] - S[i]) + a);
            dp[i][b] = worst;
            loc[i+1].push_back({worst, b});
        }
        loc[i].push_back({1e9, -1});
    }
    // for (int i = 0; i < M; i ++) {
    //     cout << "At station " << i << ":\n";
    //     for (auto [a, b]:loc[i]) {
    //         cout << a << ": ";
    //         for (int j:b) {
    //             cout << j << " ";
    //         }
    //         cout << "\n";
    //     }
    // }
}

ll arrival_time(ll Y) {
    for (int i = 0; i < M-1; i ++) {
        // find the relevant one
        int low = 0, high = N;
        while (high > low) {
            int mid = (low + high)/2;
            if (loc[i][mid].first >= Y) high = mid;
            else low = mid + 1;
        }
        if (low == 0) {
            // if it's the first bus, can travel until the end
            return (ll)X*(L - S[i]) + Y;
        }
        auto [a, b] = loc[i][low-1];
        Y = max((ll)X*(S[i+1] - S[i]) + Y, dp[i][b]);
    }
    return Y;
}

// int main() {
//     init(6, 4, {20, 10, 40, 0}, {5, 20, 20, 30}, 10, 4, {0, 1, 3, 6});
//     cout << arrival_time(0) << "\n" << arrival_time(50);
// }

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