Submission #1235799

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235799		RakhimovAmir	Overtaking (IOI23_overtaking)	C++20	65 / 100	3593 ms	39560 KiB

overtaking

#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int L, N, X, M;
vector<vector<ll>> e;
vector<vector<pair<ll, ll>>> pp;
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;
    ::T = T;
    ::W = W;
    ::X = X;
    ::M = M;
    ::S = S;
    pp.resize(M);
    e.resize(M);
    for (ll i = 0; i < M; i++) {
        e[i].resize(N);
        pp[i].resize(N);
    }
    for (ll i = 0; i < N; i++) {
        e[0][i] = T[i];
    }
    for (ll i = 1; i < M; i++) {
        vector<pair<ll, ll>> ord;
        for (ll j = 0; j < N; j++) {
            ord.push_back({e[i - 1][j], j});
        }
        sort(ord.begin(), ord.end());
        ll mx = 0, gg = 0;
        for (ll j = 0; j < N; j++) {
            ll nw = ord[j].second;
            e[i][nw] = max(mx, e[i - 1][nw] + 1ll * W[nw] * (S[i] - S[i - 1]));
            gg = max(gg, e[i][nw]);
            pp[i][j] = {ord[j].first, e[i][nw]};
            if (j)
                pp[i][j].second = max(pp[i][j].second, pp[i][j - 1].second);
            if (j < N - 1 && ord[j].first != ord[j + 1].first)
                mx = max(mx, gg);
        }
    }
    return;
}

ll arrival_time(ll Y) {
    ll tim = Y;
    for (ll i = 1; i < M; i++) {
        ll nx = tim + 1ll * X * (S[i] - S[i - 1]);
        // for (ll j = 0; j < N; j++) {
        //     if (e[i - 1][j] < tim)
        //         nx = max(nx, e[i][j]);
        // }
        auto it = lower_bound(pp[i].begin(), pp[i].end(), make_pair(tim, -1ll));
        if (it == pp[i].begin())
            tim = nx;
        else
            tim = max(nx, (--it)->second);
    }
    return tim;
}

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