Submission #1083456

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083456		SamueleVid	Overtaking (IOI23_overtaking)	C++17	39 / 100	3510 ms	520 KiB

overtaking

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

int L, N, X, M;
vector<ll> T;
vector<int> W, S;

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;
}

ll arrival_time(ll Y) {
    // cout << "Y : " << Y << '\n';
    T.push_back(Y);
    W.push_back(X);

    vector<ll> t(N + 1);
    for (int i = 0; i <= N; i ++) t[i] = T[i];
    for (int s = 1; s < M; s ++) {
        // cout << " ts : ";
        // for (auto x : t) cout << x << " ";
        // cout << '\n';
        vector<pair<ll, int>> sorted;
        for (int i = 0; i <= N; i ++) sorted.push_back({t[i], i});
        sort(sorted.begin(), sorted.end());
        ll max_e = 0;
        ll curr_max_e = 0;
        ll prev = -1;
        for (int i = 0; i <= N; i ++) {
            auto [time, idx] = sorted[i];
            // cout << "idx : " << idx << '\n';
            if (time > prev) {
                max_e = max(max_e, curr_max_e);
                prev = time;
            }

            ll curr_e = t[idx] + (ll)W[idx] * (S[s] - S[s - 1]);
            // cout << "t[idx] + (ll)W[idx] * (S[s] - S[s - 1]) : " << t[idx] << " + " << W[idx] << " + " << (S[s] - S[s - 1]) << '\n'; 
            curr_max_e = max(curr_e, curr_max_e);
            t[idx] = max(curr_e, max_e);
        }

    }

    T.pop_back();
    W.pop_back();

    return t[N];
}

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