| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 848065 | Lib | 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;
long long rspeed[1003];
long long spos[1003];
long long stime[1003];
vector <vector <long long> > arrtime; //thoi gian xe k den ben i
vector <long long> temp;
pair<long long, int> sarrtime[1003][1003];
vector <pair<long long, int> > previ;
long long ok[1003];
long long atime[1003];
long long L,N,M,X,Y;
long long T[1003];
long long W[1003];
int S[1003];
void init(int LL, int NN, std::vector<long long> TT, std::vector<int> WW, int XX, int MM, std::vector<int> SS)
{
L = LL;
N = NN;
M = MM;
X = XX;
S = SS;
long long len=L,spd=X;
int n=N+1,m=M+1;
for(int i=0;i<=n;i++){
arrtime.push_back(temp);
for(int k=0;k<=m;k++){
arrtime[i].push_back(0);
}
}
long long cmax;
for(int i=1;i<=n;i++){
stime[i]=T[i-1];
arrtime[1][i]=stime[i];
sarrtime[1][i]={stime[i],i};
previ.push_back({stime[i],i});
}
for(int i=1;i<=n;i++){
rspeed[i]=W[i-1];
}
for(int i=1;i<=m;i++){
spos[i]=S[i-1];
}
for(int i=2;i<=m;i++){
previ.push_back({0,0});
sort(previ.begin(),previ.end());
arrtime[i][previ[1].second]=arrtime[i-1][previ[1].second]+(spos[i]-spos[i-1])*rspeed[previ[1].second];
cmax=arrtime[i][previ[1].second];
for(int k=2;k<=n;k++){
cmax=max(cmax,previ[k].first+(spos[i]-spos[i-1])*rspeed[previ[k].second]);
arrtime[i][previ[k].second]=cmax;
sarrtime[i][previ[k].second]={arrtime[i][previ[k].second],previ[k].second};
}
previ.clear();
for(int k=1;k<=n;k++){
previ.push_back({arrtime[i][k],k});
}
}
return;
}
long long arrival_time(long long Y){
int M=arrtime.size()-1;
int N=arrtime[1].size()-1;
for(int i=1;i<=M;i++){
if(arrtime[1][i]>Y){
ok[i]=0;
}else{
ok[i]=1;
}
}
atime[1]=Y;
for(int i=2;i<=M;i++){
atime[i]=atime[i-1]+(spos[i]-spos[i-1])*X;
for(int k=1;k<=N;k++){
if(atime[i-1]<=arrtime[i-1][k]){
ok[k]=0;
}
if(ok[k]==1){
atime[i]=max(atime[i],arrtime[i][k]);
}
}
}
return atime[M];
}