#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) (long double)(B(k2)-B(k1))/(K(k1)-K(k2))
int h=0,top=1;//stack in fact
int q[N];
int getmin(int x) {
int l=0,r=top-2,mid;
while(l<=r) {
mid=(l+r)/2;
if(itsec(q[mid],q[mid+1])>x) r=mid-1; else l=mid+1;
}
return q[r+1];
}
signed main() {
int i,j=1,Mn;
//freopen("1.in","r",stdin);
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&&h<top) {
int ans=1e16;
// for(int k=0; k<i; k++) ans=min(ans,E(k,Mn));
// assert(ans==E(getmin(Mn),Mn));
ans=E(getmin(Mn),Mn);
f[i]=min(E(getmin(Mn),Mn)+A[i].c+i*w*Mn,f[i]);
}
while(top-h>=2&&itsec(q[top-1],q[top-2])>=itsec(i,q[top-1])) top--;
q[top++]=i;
}
cout<<f[m]+(x/t+1)*w<<endl;
return 0;
}
Compilation message
coach.cpp: In function 'int main()':
coach.cpp:44:8: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
44 | int ans=1e16;
| ^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
304 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
312 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
312 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
304 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
312 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
312 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
308 KB |
Output is correct |
25 |
Correct |
1 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
212 KB |
Output is correct |
27 |
Correct |
1 ms |
212 KB |
Output is correct |
28 |
Correct |
1 ms |
308 KB |
Output is correct |
29 |
Correct |
1 ms |
212 KB |
Output is correct |
30 |
Correct |
1 ms |
308 KB |
Output is correct |
31 |
Correct |
0 ms |
212 KB |
Output is correct |
32 |
Correct |
1 ms |
212 KB |
Output is correct |
33 |
Correct |
1 ms |
212 KB |
Output is correct |
34 |
Correct |
0 ms |
212 KB |
Output is correct |
35 |
Correct |
1 ms |
212 KB |
Output is correct |
36 |
Correct |
1 ms |
212 KB |
Output is correct |
37 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
304 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
312 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
312 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
308 KB |
Output is correct |
25 |
Correct |
1 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
212 KB |
Output is correct |
27 |
Correct |
1 ms |
212 KB |
Output is correct |
28 |
Correct |
1 ms |
308 KB |
Output is correct |
29 |
Correct |
1 ms |
212 KB |
Output is correct |
30 |
Correct |
1 ms |
308 KB |
Output is correct |
31 |
Correct |
0 ms |
212 KB |
Output is correct |
32 |
Correct |
1 ms |
212 KB |
Output is correct |
33 |
Correct |
1 ms |
212 KB |
Output is correct |
34 |
Correct |
0 ms |
212 KB |
Output is correct |
35 |
Correct |
1 ms |
212 KB |
Output is correct |
36 |
Correct |
1 ms |
212 KB |
Output is correct |
37 |
Correct |
1 ms |
212 KB |
Output is correct |
38 |
Correct |
3 ms |
340 KB |
Output is correct |
39 |
Correct |
3 ms |
340 KB |
Output is correct |
40 |
Correct |
4 ms |
448 KB |
Output is correct |
41 |
Correct |
3 ms |
320 KB |
Output is correct |
42 |
Correct |
3 ms |
320 KB |
Output is correct |
43 |
Correct |
2 ms |
340 KB |
Output is correct |
44 |
Correct |
3 ms |
340 KB |
Output is correct |
45 |
Correct |
2 ms |
408 KB |
Output is correct |
46 |
Correct |
2 ms |
324 KB |
Output is correct |
47 |
Correct |
3 ms |
340 KB |
Output is correct |
48 |
Correct |
3 ms |
320 KB |
Output is correct |
49 |
Correct |
3 ms |
340 KB |
Output is correct |
50 |
Correct |
3 ms |
340 KB |
Output is correct |
51 |
Correct |
3 ms |
344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
304 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
312 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
0 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
1 ms |
312 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
308 KB |
Output is correct |
25 |
Correct |
1 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
212 KB |
Output is correct |
27 |
Correct |
1 ms |
212 KB |
Output is correct |
28 |
Correct |
1 ms |
308 KB |
Output is correct |
29 |
Correct |
1 ms |
212 KB |
Output is correct |
30 |
Correct |
1 ms |
308 KB |
Output is correct |
31 |
Correct |
0 ms |
212 KB |
Output is correct |
32 |
Correct |
1 ms |
212 KB |
Output is correct |
33 |
Correct |
1 ms |
212 KB |
Output is correct |
34 |
Correct |
0 ms |
212 KB |
Output is correct |
35 |
Correct |
1 ms |
212 KB |
Output is correct |
36 |
Correct |
1 ms |
212 KB |
Output is correct |
37 |
Correct |
1 ms |
212 KB |
Output is correct |
38 |
Correct |
3 ms |
340 KB |
Output is correct |
39 |
Correct |
3 ms |
340 KB |
Output is correct |
40 |
Correct |
4 ms |
448 KB |
Output is correct |
41 |
Correct |
3 ms |
320 KB |
Output is correct |
42 |
Correct |
3 ms |
320 KB |
Output is correct |
43 |
Correct |
2 ms |
340 KB |
Output is correct |
44 |
Correct |
3 ms |
340 KB |
Output is correct |
45 |
Correct |
2 ms |
408 KB |
Output is correct |
46 |
Correct |
2 ms |
324 KB |
Output is correct |
47 |
Correct |
3 ms |
340 KB |
Output is correct |
48 |
Correct |
3 ms |
320 KB |
Output is correct |
49 |
Correct |
3 ms |
340 KB |
Output is correct |
50 |
Correct |
3 ms |
340 KB |
Output is correct |
51 |
Correct |
3 ms |
344 KB |
Output is correct |
52 |
Correct |
310 ms |
12332 KB |
Output is correct |
53 |
Correct |
363 ms |
12236 KB |
Output is correct |
54 |
Correct |
286 ms |
11420 KB |
Output is correct |
55 |
Correct |
297 ms |
11644 KB |
Output is correct |
56 |
Correct |
288 ms |
11948 KB |
Output is correct |
57 |
Correct |
294 ms |
11628 KB |
Output is correct |
58 |
Correct |
302 ms |
12232 KB |
Output is correct |
59 |
Correct |
296 ms |
11700 KB |
Output is correct |
60 |
Correct |
278 ms |
11408 KB |
Output is correct |
61 |
Correct |
284 ms |
11592 KB |
Output is correct |
62 |
Correct |
297 ms |
11616 KB |
Output is correct |
63 |
Correct |
299 ms |
12096 KB |
Output is correct |
64 |
Correct |
307 ms |
12376 KB |
Output is correct |
65 |
Correct |
393 ms |
12248 KB |
Output is correct |
66 |
Correct |
400 ms |
12292 KB |
Output is correct |
67 |
Correct |
385 ms |
12288 KB |
Output is correct |
68 |
Correct |
413 ms |
12240 KB |
Output is correct |
69 |
Correct |
300 ms |
11992 KB |
Output is correct |
70 |
Correct |
315 ms |
12048 KB |
Output is correct |
71 |
Correct |
302 ms |
12012 KB |
Output is correct |
72 |
Correct |
303 ms |
12164 KB |
Output is correct |
73 |
Correct |
298 ms |
11984 KB |
Output is correct |
74 |
Correct |
299 ms |
12088 KB |
Output is correct |
75 |
Correct |
302 ms |
12184 KB |
Output is correct |
76 |
Correct |
305 ms |
12144 KB |
Output is correct |
77 |
Correct |
293 ms |
12032 KB |
Output is correct |
78 |
Correct |
312 ms |
12196 KB |
Output is correct |
79 |
Correct |
297 ms |
11596 KB |
Output is correct |
80 |
Correct |
298 ms |
11580 KB |
Output is correct |