| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 915698 | chirathnirodha | Overtaking (IOI23_overtaking) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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(ll L, ll N, vector<ll> T, vector<ll> W, ll X, ll M, vector<ll> SP){
n=N;m=M;l=L;spn=X;
for(int i=0;i<n;i++){
sp.PB(W[i]);
t[0].PB(T[i]);
len.PB(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]);
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;
nt.PB(vt[j][pos]);
}
return nt[m-1];
}