Submission #1080757

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080757		Boomyday	Overtaking (IOI23_overtaking)	C++17	65 / 100	3556 ms	14672 KiB

overtaking

//#include "overtaking.h"

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

using ll = long long;

ll SZ = 1001;
vector<vector<ll>> arrival(SZ+1, vector<ll>(SZ+1,-1)); //arrival[time][bus]
vector<vector<int>> sortOrders;
ll n, X_, M_;
vector<ll> t, w;
vector<ll> S_;
vector<ll> w_;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    S_ = vector<ll>(S.begin(),S.end());
    X_ = X;
    M_ = M;


    // sort the buses by leaving time (smallest to largest) then speed (largest to smallest)
    // the arrival time for each bus is the prefix maximum of this array
    for(int i=0;i<N;++i){
        if (W[i] > X){
            t.push_back(T[i]);
            w.push_back(W[i]);
        }
    }
    w_ = vector<ll>(w.begin(),w.end());
    n = t.size();

    // output w and t


    for(int i=0;i<n;++i){
        arrival[0][i] = t[i];
    }
    for(int j=1;j<M;++j){
        //cout << "Foo" << endl;
        vector<int> buses(n);
        for(int i=0;i<n;++i) buses[i] = i;
        // output buses

        std::sort(buses.begin(), buses.end(), [&](int a, int b)->bool{
            //cout << a << " " << b << endl;
            if (arrival[j-1][a] < arrival[j-1][b]) return 1;
            if (arrival[j-1][a] > arrival[j-1][b]) return 0;
            if (w[a] < w[b]) return 1;
            return 0;
        });
        //cout << "Foo" << endl;
        sortOrders.push_back(buses);
        ll pmax = 0;

        for (auto& bus:buses){
            arrival[j][bus] = max(pmax, arrival[j-1][bus]+w[bus]*(S[j]-S[j-1]));
            pmax = max(pmax, arrival[j][bus]);
        }
    }

    // output the arrival array




    return;
}

long long arrival_time(long long Y)
{
    ll tm = Y;
    for(int j=1;j<M_;++j){


        int bnd = upper_bound(sortOrders[j-1].begin(), sortOrders[j-1].end(),-1,[&](int a, int b)->bool{
            if (tm <= arrival[j-1][b]) return 1;
            

            return 0;
        }) - sortOrders[j-1].begin();





        if (bnd == 0) {
            tm +=
                    X_*(S_[j]-S_[j-1]);
        } else {

            tm = max(tm+ X_*(S_[j]-S_[j-1]), arrival[j][sortOrders[j-1][bnd-1]]);
        }
    }
    return tm;
}


/*
int main()
{
    int L, N, X, M, Q;
    assert(5 == scanf("%d %d %d %d %d", &L, &N, &X, &M, &Q));
    std::vector<long long> T(N);
    for (int i = 0; i < N; i++)
        assert(1 == scanf("%lld", &T[i]));
    std::vector<int> W(N);
    for (int i = 0; i < N; i++)
        assert(1 == scanf("%d", &W[i]));
    std::vector<int> S(M);
    for (int i = 0; i < M; i++)
        assert(1 == scanf("%d", &S[i]));
    std::vector<long long> Y(Q);
    for (int i = 0; i < Q; i++)
        assert(1 == scanf("%lld", &Y[i]));

    fclose(stdin);

    init(L, N, T, W, X, M, S);
    std::vector<long long> res(Q);
    for (int i = 0; i < Q; i++)
        res[i] = arrival_time(Y[i]);

    for (int i = 0; i < Q; i++)
        printf("%lld\n", res[i]);
    fclose(stdout);
    return 0;
}
*/

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