Submission #1132807

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132807		SpyrosAliv	Overtaking (IOI23_overtaking)	C++20	0 / 100	1 ms	328 KiB

overtaking

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

vector<ll> start; // start time of each bus
vector<int> speed;//bus speed
vector<int> stops;
int len; // size of road
int n, m; // number of buses and stations
int xsp; // reserve travel time

void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S) {
    len = L;
    n = N;
    start = T;
    speed = W;
    xsp = X;
    m = M;
    stops = S;
}

ll arrival_time(ll st) {
    vector<tuple<ll, int, bool>> currTimes;
    for (int i = 0; i < n; i++) {
        currTimes.push_back({start[i], speed[i], false});
    }
    currTimes.push_back({st, xsp, true});

    for (int i = 0; i < m-1; i++) {
        sort(currTimes.begin(), currTimes.end());
        vector<tuple<ll, int, bool>> nxt;
        ll maxTime = -1;
        int dis = stops[i+1] - stops[i];

        for (auto [currTime, sp, special]: currTimes) {
            ll nxtTime = currTime + sp * dis;
            if (currTime <= maxTime) nxtTime = max(nxtTime, maxTime);
            maxTime = max(maxTime, nxtTime);
            nxt.push_back({nxtTime, sp, special});
        }

        currTimes = nxt;
    }
    for (auto [a, b, c]: currTimes) {
        if (c == true) {
            return a;
        }
    }
    return -1;
}
/*
int main() {
    init(6, 4, {20, 10, 40, 0}, {5, 20, 20, 30}, 10, 4, {0, 1, 3, 6});
    cout << arrival_time(0) << '\n';
    cout << arrival_time(50) << "\n";

}*/

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