| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 783647 | kshitij_sodani | Long Distance Coach (JOI17_coach) | C++14 | 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 a first
#define b second
#define pb push_back
typedef long long llo;
#define endl '\n'
llo it[200001];
llo dp[200001];
llo xx[200001];
llo pre[200001];
llo pre2[200001];
pair<llo,llo> sect(pair<llo,llo> aa,pair<llo,llo> bb){
pair<llo,llo> zz={bb.b-aa.b,aa.a-bb.a};
if(zz.b<0){
zz.b=-zz.b;
zz.a=-zz.a;
}
return zz;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
llo x,n,m,w,t;
cin>>x>>n>>m>>w>>t;
vector<pair<pair<llo,llo>,llo>> ss;
llo ans=((x/t)+1)*w;
for(llo i=0;i<n;i++){
cin>>it[i];
ss.pb({{it[i]%t,-1},it[i]/t});
}
ss.pb({{x%t,-1},x/t});
for(llo i=0;i<m;i++){
llo aa,bb;
cin>>aa>>bb;
if((aa)<(x%t)){
ans+=((x/t)*w)+w;
xx[i]=(x/t);
}
else{
ans+=(((x/t))*w);
xx[i]=(x/t)-1;
}
ss.pb({{aa,xx[i]},bb});
}
//cout<<ans<<endl;
sort(ss.begin(),ss.end());
dp[0]=0;
llo ma=0;
/*for(auto j:ss){
cout<<j.a.a<<":"<<j.a.b<<":"<<j.b<<endl;
}*/
pre[0]=0;
pre2[0]=0;
for(int i=0;i<ss.size();i++){
pre[i+1]=pre[i];
pre2[i+1]=pre2[i];
if(ss[i].a.b>=0){
pre[i+1]+=ss[i].b;
pre[i+1]-=w*ss[i].a.b;
pre2[i+1]=pre2[i]+1;
}
}
vector<pair<llo,llo>> ss2;
vector<pair<llo,llo>> tt;
for(llo i=0;i<ss.size();i++){
dp[i+1]=dp[i];
if(ss[i].a.b>=0){
pair<llo,llo> cur={-w*pre2[i],-pre[i]-dp[i]};
while(ss2.size()>=2){
pair<llo,llo> aa=sect(ss2[ss2.size()-2],ss2.back());
pair<llo,llo> bb=sect(ss2[ss2.size()-2],cur);
int128_t xx=aa.b*bb.a;
int128_t yy=bb.b*aa.a;
if(xx<=yy){
ss2.pop_back();
tt.pop_back();
}
else{
break;
}
//check if bb<aa
}
if(ss2.size()){
tt.pb(sect(ss2.back(),cur));
}
ss2.pb(cur);
}
if(ss[i].a.b==-1){
//llo su=0;
llo ma=1e18;
for(auto jj:ss2){
ma=min(ma,jj.a*(ss[i].b-1)+jj.b);
}
llo cot=ma;
dp[i+1]=max(dp[i+1],-cot+(-ss[i].b+1)*pre2[i+1]*w-pre[i+1]);
/*for(llo j=i-1;j>=0;j--){
llo su=-w*pre2[j]*(-ss[i].b+1);
//query max here
pair<llo,llo> cur={-w*pre2[j],-pre[j]-dp[j]};
//query is (ss[i].b-1)
//slope is -ss[i].b+1
//number of type 0 in prefix
//dp[i+1]=max(dp[i+1],-cot+(-ss[i].b+1)*pre2[i+1]*w-pre[i+1]);
//dp[i+1]=max(dp[i+1],dp[j]+su+(-ss[i].b+1)*pre2[i+1]*w+pre[j]-pre[i+1]);
}*/
}
ma=max(ma,dp[i+1]);
//cout<<dp[i+1]<<",";
}
//cout<<endl;
ans-=ma;
cout<<ans<<endl;
return 0;
}