Submission #1046317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046317		slivajan	Overtaking (IOI23_overtaking)	C++17	65 / 100	3531 ms	34132 KiB

overtaking

#include "overtaking.h"

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

typedef long long un;
typedef vector<un> vuc;
typedef tuple<un, un, un> tup;

#define REP(i, a, b) for (un i = (un)a; i < (un)b; i++)
#define FEAC(i, a) for (auto&& i : a)
#define vec vector
#define ALL(x) (x).begin(), (x).end()

constexpr un INF = INT64_MAX;

vec<vuc> prij;
vec<vec<tup>> seraz;
un speed;
vuc _S;
un _M;


void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
    speed = X;

    _S = vuc(M);
    REP(i, 0, M) _S[i] = S[i];

    vuc _W(N);
    REP(i, 0, N) _W[i] = W[i];
    
    _M = M;

   prij = vec<vuc>(M, vuc(N, -1));
   prij[0] = T;

   REP(e, 0, M-1){
        vec<tup> toSort;
        REP(i, 0, N){
            toSort.push_back({prij[e][i], _W[i], i});
        }
        sort(ALL(toSort));

        seraz.push_back(toSort);

        un limit = 0;
        REP(i, 0, N){
            un odjezd, index;
            tie(odjezd, ignore, index) = toSort[i];

            limit = max(limit, odjezd + _W[index] * (_S[e+1] - _S[e]));
            prij[e+1][index] = limit;
        }
   }

}

long long arrival_time(long long Y)
{
    un now = Y;
    REP(e, 0, _M-1){
        tup what = {now, speed, -1};

        auto ptr = upper_bound(ALL(seraz[e]), what);
        if (ptr == seraz[e].begin()){
            now += speed * (_S[e+1] - _S[e]);
        }
        else{
            ptr--;
            un snek;
            tie(ignore, ignore, snek) = *ptr;
            now = max(now + speed * (_S[e+1] - _S[e]), prij[e+1][snek]);
        }
    }

    return now;
}

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