Submission #980966

#	Time	Username	Problem	Language	Result	Execution time	Memory
980966		vjudge1	Overtaking (IOI23_overtaking)	C++17	0 / 100	0 ms	600 KiB

overtaking

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

using ll = long long;

int MT,XT;
vector<int>ST(1005);
set<pair<ll,ll>>st[1005];

void init(int L,int N,vector<ll> T,vector<int> W,int X,int M,vector<int> S){
    for(int i=0;i<M;i++)ST[i]=S[i];
    MT=M,XT=X;
    vector<pair<ll,int>>tw(N);
    for(int i=0;i<N;i++)tw[i]={T[i],W[i]};
    sort(tw.begin(),tw.end());
    for(int i=1;i<M;i++){
        ll t=-1,mp=0,la=0,lan=0;
        vector<pair<ll,int>>ntw(N);
        for(int j=0;j<N;j++){
            if(t==-1)t=tw[j].first;
            if(t<tw[j].first){
                la=max(la,lan);
                st[i-1].insert({t,la});
                t=tw[j].first;
            }
            ntw[j]={max(tw[j].first+tw[j].second*(S[i]-S[i-1]),mp),tw[j].second};
            mp=max(mp,ntw[j].first);
            lan=max(lan,ntw[j].first);
        }
        la=max(la,lan);
        st[i-1].insert({t,la});
        swap(tw,ntw);
        sort(tw.begin(),tw.end());
    }
    return;
}

long long arrival_time(long long Y){
    for(int i=0;i<MT-1;i++){
        auto r=st[i].lower_bound({Y,0});
        ll d=Y+XT*(ST[i+1]-ST[i]);
        if(r==st[i].begin())Y=d;
        else{
            r--;
            Y=max(d,(*r).second);
        }
    }
    return Y;
}

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