#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 200110;
int s[N],f[N];
struct passenger {
int d,c;
bool operator < (const passenger &ri) const {
return d<ri.d;
}
} A[N];
int x,n,m,w,t;
bool cmp(int a,int b) {
return a%t<b%t;
}
#define K(p) (-p*w)
#define B(p) (f[p]-A[p].c)
#define E(p,x) (K(p)*(x)+B(p))
#define itsec(k1,k2) (double)(B(k2)-B(k1))/(K(k1)-K(k2))
int h=1,top=1;//stack in fact
int q[N];
int getmin(int x) {
int l=1,r=top,mid;
while(l<=r) {
mid=(l+r)/2;
if(itsec(mid,mid+1)<=x) {
l=mid+1;
} else {
r=mid-1;
}
}
return l-1;
}
signed main() {
int i,j=1,Mn;
cin>>x>>n>>m>>w>>t;
for(i=1; i<=n; i++) cin>>s[i];
for(i=1; i<=m; i++) cin>>A[i].d>>A[i].c;
A[m+1].d=t,f[0]=0,s[++n]=x;
sort(s+1,s+n+1,cmp),sort(A+1,A+m+1);
for(i=1; i<=m; i++) A[i].c+=A[i-1].c;
while(s[j]%t<=A[1].d&&j<=n) j++;
for(i=1; i<=m; i++) {
for(Mn=1e16; j<=n&&s[j]%t<=A[i+1].d; j++) Mn=min(Mn,s[j]/t);
f[i]=f[i-1]+((x-A[i].d)/t+1)*w;
if(Mn!=1e16) {
int ans=1e16;
for(int k=0; k<i; k++) ans=min(ans,E(k,Mn));
assert(ans==E(getmin(Mn),Mn));
f[i]=min(ans+A[i].c+i*w*Mn,f[i]);
while(top-h>=2&&itsec(top-1,top-2)>=itsec(i,top-1)) top--;
q[top++]=i;
}
}
cout<<f[m]+(x/t+1)*w<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
