| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 27681 | suhgyuho_william | 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>
#define lld long long
#define pii pair<int,int>
#define pll pair<lld,lld>
#define pb push_back
#define next nextt
#define Inf 1000000000
#define Linf 1000000000000000000LL
#define Mod 1000000007
using namespace std;
int N,M;
lld X,W,T;
lld a[200002],d[200002],memo[200002],sum[200002];
struct data{
lld d,c;
data(){}
data(lld d,lld c):d(d),c(c){}
bool operator < (const data &cmp) const{
return d < cmp.d;
}
}b[200002];
pll tmp[200002];
struct CHTaaa{
int cr = -1;
pll tmp[200002];
lld f(int num,lld x){
return tmp[num].first*x+tmp[num].second;
}
lld ccw(pll x,pll y,pll z){
return (x.first*y.second+y.first*z.second+z.first*x.second)
-(y.first*x.second+z.first*y.second+x.first*z.second);
}
void add(lld x,lld y){
while(cr > 0 && ccw(tmp[cr-1],tmp[cr],pll(x,y)) >= 0) cr--;
cr++;
tmp[cr] = pll(x,y);
}
lld get(lld x){
int l,r;
l = 0; r = cr;
while(l < r){
int m = (l+r)>>1;
if(f(m,x) < f(m+1,x)) r = m;
else l = m+1;
}
return f(l,x);
}
}cht;
lld get(lld x){
return ((X-x)/T+1)*W;
}
int main(){
long long iX,iW,iT;
scanf("%lld %d %d %lld %lld",&iX,&N,&M,&iW,&iT);
X = iX; W = iW; T = iT;
for(int i=1; i<=N; i++){
long long ia;
scanf("%lld",&ia);
a[i] = ia;
}
sort(a+1,a+N+1);
for(int i=1; i<=M; i++){
long long id,ic;
scanf("%lld %lld",&id,&ic);
b[i].d = id; b[i].c = ic;
}
sort(b+1,b+M+1);
a[N+1] = X;
for(int i=1; i<=M; i++){
memo[i] = Linf;
sum[i] = sum[i-1]+b[i].c;
}
for(int i=1; i<=N+1; i++){
int it;
it = lower_bound(b+1,b+M+1,data(a[i]%T,0))-b-1;
memo[it] = min(memo[it],(a[i]/T)*W);
}
d[0] = get(0);
cht.add(0,d[0]);
for(int i=1; i<=M; i++){
d[i] = Linf;
if(memo[i] != Linf){
d[i] = cht.get(memo[i]);
d[i] += sum[i]+memo[i]*i;
}
d[i] = min(d[i],d[i-1]+get(b[i].d));
cht.add(-i,d[i]-sum[i]);
}
long long print = d[M];
printf("%lld\n",print);
return 0;
}