제출 #1182412

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1182412		Lithanium	추월 (IOI23_overtaking)	C++20	65 / 100	3596 ms	118020 KiB

overtaking

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

using ll = long long;

map<ll, vector<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][T[i]].push_back(i);
    }
    for (int i = 0; i < M-1; i ++) {
        ll worst = 0;
        for (auto &[a, b]:loc[i]) {
            sort(b.begin(), b.end(), [&](const int a, const int b) {
                // sort by increasing gradient
                return W[a] < W[b];
            });
            for (int j:b) {
                worst = max(worst,(ll)W[j]*(S[i+1] - S[i]) + a);
                dp[i][j] = worst;
                loc[i+1][worst].push_back(j);
            }
        }
    }
    // 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
        auto it = loc[i].lower_bound(Y);
        if (it == loc[i].begin()) {
            // if it's the first bus, can travel until the end
            return (ll)X*(L - S[i]) + Y;
        }
        it --;
        auto [a, b] = *it;
        Y = max((ll)X*(S[i+1] - S[i]) + Y, dp[i][b.back()]);
    }
    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