#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll N = 200005, inf = 1e18;
ll x, n, m, w, t, rf[N];
ll sum[N], mn[N], dt[N];
pll a[N];
struct cht {
vector<pll> v;
ll val (pll &A, ll &P) {return A.X*P+A.Y;}
bool valid (pll &A, pll &B, pll &C) {
return (B.Y-A.Y)*(A.X-C.X) < (C.Y-A.Y)*(A.X-B.X);
}
void upd (ll G, ll B) {
pll T = pll(G, B);
for(ll i=v.size();i-->1;) {
if(valid(v[i-1], v[i], T)) break;
else v.pop_back();
}
v.push_back(T);
}
ll get (ll P) {
ll S = 0, E = (ll)v.size()-1;
while(S<E) {
ll T = (S+E)/2;
val(v[T],P)<val(v[T+1],P) ? E = T : S = T+1;
}
return val(v[S], P);
}
} h;
ll cost (ll P) {return (x/t+(x%t>=P))*w;}
int main()
{
scanf("%lld%lld%lld%lld%lld",&x,&n,&m,&w,&t);
for(ll i=1;i<=n;i++) scanf("%lld",&rf[i]);
for(ll i=1;i<=m;i++) scanf("%lld%lld",&a[i].X,&a[i].Y);
sort(a+1, a+1+m);
for(ll i=1;i<=m;i++) {
sum[i] = sum[i-1] + a[i].Y;
mn[i] = inf;
}
rf[n+1] = x;
for(ll i=1;i<=n+1;i++) {
ll I = lower_bound(a+1, a+1+m, pll(rf[i]%t, 0)) - a - 1;
mn[I] = min(mn[I], rf[i]/t);
}
dt[0] = cost(0); h.upd(0, dt[0]);
for(ll i=1;i<=m;i++) {
dt[i] = dt[i-1]+cost(a[i].X);
if(mn[i] != inf) dt[i] = min(dt[i], h.get(mn[i])+mn[i]*i*w+sum[i]);
h.upd(-i*w, dt[i]-sum[i]);
}
printf("%lld\n",dt[m]);
}
Compilation message
coach.cpp: In function 'int main()':
coach.cpp:41:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld%lld%lld",&x,&n,&m,&w,&t);
^
coach.cpp:42:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(ll i=1;i<=n;i++) scanf("%lld",&rf[i]);
^
coach.cpp:43:56: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(ll i=1;i<=m;i++) scanf("%lld%lld",&a[i].X,&a[i].Y);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 2 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 3 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 4 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 5 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 6 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 7 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 8 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 9 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 10 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 11 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 12 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 13 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 14 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 15 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 16 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 17 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 18 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 19 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 20 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 21 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 22 |
Correct |
0 ms |
11400 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 2 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 3 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 4 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 5 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 6 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 7 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 8 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 9 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 10 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 11 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 12 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 13 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 14 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 15 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 16 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 17 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 18 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 19 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 20 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 21 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 22 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 23 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 24 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 25 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 26 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 27 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 28 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 29 |
Incorrect |
0 ms |
11400 KB |
Output isn't correct |
| 30 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 2 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 3 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 4 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 5 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 6 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 7 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 8 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 9 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 10 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 11 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 12 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 13 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 14 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 15 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 16 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 17 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 18 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 19 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 20 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 21 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 22 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 23 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 24 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 25 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 26 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 27 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 28 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 29 |
Incorrect |
0 ms |
11400 KB |
Output isn't correct |
| 30 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 2 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 3 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 4 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 5 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 6 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 7 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 8 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 9 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 10 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 11 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 12 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 13 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 14 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 15 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 16 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 17 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 18 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 19 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 20 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 21 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 22 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 23 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 24 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 25 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 26 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 27 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 28 |
Correct |
0 ms |
11400 KB |
Output is correct |
| 29 |
Incorrect |
0 ms |
11400 KB |
Output isn't correct |
| 30 |
Halted |
0 ms |
0 KB |
- |
