# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
851109 | oneloveforever | 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<bits/stdc++.h>
using namespace std;
#define ll int64
#define x first
#define y second
const int MAXN=1e3+7;
set<pair<long long ,long long> >place[MAXN];
ll M,X;
vector<ll>S;
void init(int L,int N,vector<long long>T,vector<int>W,int _X,int _M,vector<int>_S)
{
M=_M;
X=_X;
S=_S;
vector<pair<long long,long long> >block;
for(int i=0;i<=N-1;i++)block.push_back({W[i],T[i]});
sort(block.begin(),block.end());
for(int i=0;i<=M-1;i++)place[i].insert(make_pair(0,0));
for(int i=(int)block.size()-1;i>=0;i--)
{
long long Time=block[i].y;
long long C=block[i].x;
for(int cnt=1;cnt<=M-1;cnt++)
{
auto pre=prev(place[cnt].lower_bound(make_pair(Time,0)));
long long newTime=max(pre->y,Time+C*(S[cnt]-S[cnt-1]));
place[cnt].insert(make_pair(Time,newTime));
Time=newTime;
}
}
}
long long arrival_time(long long Time)
{
for(int cnt=1;cnt<=M-1;cnt++)
{
auto pre=prev(place[cnt].lower_bound(make_pair(Time,0)));
long long newTime=max(pre->y,Time+X*(S[cnt]-S[cnt-1]));
Time=newTime;
}
return Time;
}
/*int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int L,N;
vector<long long>T;
vector<int>W;
int X,M;
vector<int>S;
cin>>L>>N;
for(int i=1;i<=N;i++)
{
long long value;
cin>>value;
T.push_back(value);
}
for(int i=1;i<=N;i++)
{
long long value;
cin>>value;
W.push_back(value);
}
cin>>X>>M;
for(int i=1;i<=M;i++)
{
int value;
cin>>value;
S.push_back(value);
}
init(L,N,T,W,X,M,S);
int Time;
cin>>Time;
cout<<arrival_time(Time);
}*/