# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
861457 | gurkot | Overtaking (IOI23_overtaking) | C++17 | 3 ms | 11356 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 <iostream>
#include <algorithm>
#include <vector>
//#include <cstdlib>
using namespace std;
int n,m,x;
long long t[1001][1001]; int w[1001][1001];
int s[1001];
void init(int L, int N, std::vector<long long> T, std::vector<int> W,
int X, int M, std::vector<int> S) {
n=0; m=M; x=X;
for (int i=0;i<M;i++)s[i]=S[i];
int nom;
for (int i=0;i<N;i++)
if (W[i]>X) {
w[0][n]=W[i];t[0][n]=T[i];
nom=n;
while (nom>0)
if (t[0][nom]==t[0][nom-1] && w[0][nom]>w[0][nom-1])
{swap(t[0][nom],t[0][nom-1]);swap(w[0][nom],w[0][nom-1]);nom--;}
else break;
n++;
}
//counting without reserve bus (precalculation)
for (int i=1;i<m;i++) {
w[i][0]=w[i-1][0];
t[i][0]=t[i-1][0]+(long long)w[0][0]*(s[i]-s[i-1]);
for (int j=1;j<n;j++){
w[i][j]=w[i-1][j];
t[i][j]=max(t[i][j-1],t[i-1][j]+(long long)w[i][j]*(s[i]-s[i-1]));
nom=j;
while (nom>0)
if (t[i][nom]==t[i][nom-1] && w[i][nom]<w[i][nom-1])
{swap(t[i][nom],t[i][nom-1]);swap(w[i][nom],w[i][nom-1]);nom--;}
else break;
}
}//i
return;
}
long long arrival_time(long long Y){
long long rt=Y;
int nomr=n;
while (nomr>0)
if (rt<=t[0][nomr-1]) nomr--;
else break;
if (nomr==0) return rt+(long long)s[m-1]*x;
for (int i=1;i<m;i++){
rt=max(rt+(long long)(s[i]-s[i-1])*x,t[i][nomr-1]);
while (nomr>0)
if (rt==t[i][nomr-1]) nomr--;
else break;
if (nomr==0) return rt+(long long)(s[m-1]-s[i])*x;
}//i
return rt;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |