이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=1000+10;
long long n,dis[maxn],shib,m;
pair<long long,long long>all[maxn];
map<long long,vector<long long>>mp[maxn];
vector<pair<long long,long long>>mpmx[maxn];
long long solve(long long ind,long long y){
// cout<<"solve: "<<ind<<" "<<y<<endl;
if(ind==m-1){
return y;
}
long long fake=shib*(dis[ind+1]-dis[ind])+y;
/* for(auto x:mpmx[ind]){
if(x.first>=y){
break;
}
fake=max(fake,x.second);
}*/
int p=lower_bound(mpmx[ind].begin(),mpmx[ind].end(),make_pair(y,-1ll))-mpmx[ind].begin();
if(p!=0){
p--;
fake=max(fake,mpmx[ind][p].second);
}
return solve(ind+1,fake);
}
void build(){
for(long long i=0;i<m;i++){
long long mx=0;
for(auto x:mp[i]){
long long fake=mx;
for(auto y:x.second){
mp[i+1][max(fake,x.first+(dis[i+1]-dis[i])*y)].push_back(y);
mx=max(mx,x.first+(dis[i+1]-dis[i])*y);
// cout<<"wtf: "<<i<<" "<<x.first<<" "<<y<<endl;
}
mpmx[i].push_back(make_pair(x.first,mx));
}
}
}
void init(int L,int N, std::vector<long long> T, std::vector<int> W,int X,int M, std::vector<int> S)
{
n=N;
for(long long i=0;i<n;i++){
mp[0][T[i]].push_back(W[i]);
all[i]=make_pair(T[i],W[i]);
}
shib=X;
m=M;
for(long long i=0;i<m;i++){
dis[i]=S[i];
}
build();
return;
}
long long arrival_time(long long Y)
{
return solve(0,Y);
}
# | 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... |