Submission #915723

#	Time	Username	Problem	Language	Result	Execution time	Memory
915723		chirathnirodha	Overtaking (IOI23_overtaking)	C++17	65 / 100	3528 ms	50996 KiB

overtaking

#include "overtaking.h" 
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair
#define P push
#define I insert
#define F first
#define S second
typedef long long ll;
 
ll n,m,l,spn;
vector<ll> sp;
vector<ll> t[1000],e[1000];
vector<pair<ll,ll > > v[1000];
vector<ll> vt[1000];
vector<ll> len;
void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> SP){
    n=(ll)N;m=(ll)M;l=(ll)L;spn=(ll)X;
    for(int i=0;i<n;i++){
        sp.PB((ll)W[i]);
        t[0].PB(T[i]);
    }
  	for(int i=0;i<m;i++)len.PB((ll)SP[i]);
    for(int j=1;j<m;j++){
        vector<pair<ll,pair<ll,ll> > > temp;
        for(int i=0;i<n;i++){
            e[j].PB(t[j-1][i]+(len[j]-len[j-1])*sp[i]);
            t[j].PB(-1);
            temp.PB(MP(t[j-1][i],MP(sp[i],i)));
        }
        sort(temp.begin(),temp.end());
        ll cur=-1;
        for(int i=0;i<n;i++){
            int y=temp[i].S.S;
            cur=max(cur,e[j][y]);
            t[j][y]=cur;
            v[j].PB(MP(t[j-1][y],sp[y]));
            vt[j].PB(t[j][y]);
        }
    }
    return;
}
 
long long arrival_time(long long Y){
    vector<ll> nt;nt.PB(Y);
    for(int j=1;j<m;j++){
        pair<ll,ll> p={nt[j-1],spn};
        auto up=upper_bound(v[j].begin(),v[j].end(),p);
        int pos=up-v[j].begin()-1;
        ll ne=nt[j-1]+(len[j]-len[j-1])*spn;
        if(pos==-1)nt.PB(ne);
        else nt.PB(max(ne,vt[j][pos]));
    }
    return nt[m-1];
}

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