#include<bits/stdc++.h> #define ll long long #define pb push_back #define ii pair<int, int> #define fi first #define se second #define all(a) a.begin(), a.end() #define int ll using namespace std; const int N = 5e5+5; const int mod = 1e9+7; const int inf = 2e9; const double INF = 1/.0; struct Line { int a,b; mutable double p; bool operator< (const Line& o) const { if (o.a == inf && o.b == inf) return p < o.p; return a < o.a; } }; struct CHTMax { multiset<Line> s; bool isect(multiset<Line>::iterator x, multiset<Line>::iterator y) { if (y == s.end()) return x->p = INF, false; if (x->a == y->a) x->p = (x->b > y->b) ? INF : -INF; else x->p = (double) (y->b - x->b) / (x->a - y->a); return x->p >= y->p; } void add(int a, int b) { auto x = s.insert({a, b, 0}), y = next(x); while (isect(x, y)) y = s.erase(y); if ((y = x) != s.begin() && isect(--y, x)) isect(y, s.erase(x)); while ((x = y) != s.begin() && (--x)->p >= y->p) { isect(x, s.erase(y)); y = x; } } int query(int x) { // if (s.empty()) return -inf; Line l = *s.lower_bound({ inf, inf, x }); return l.a * x + l.b; } }; int x,n,m,w,t; int s[N], pc[N], dp[N], block[N]; vector<ii> p; void solve() { cin>>x>>n>>m>>w>>t; for (int i = 1; i <= n; i++) cin>>s[i]; sort(s+1, s+n+1); s[n+1] = x; for (int i = 1; i <= m; i++) { int d,c; cin>>d>>c; p.pb({d, c}); } p.pb({-1, -1}); sort(all(p)); for (int i = 1; i <= m; i++) pc[i] = pc[i-1] + p[i].se, block[i] = -1; for (int i = 1; i <= n+1; i++) { int pos = upper_bound(all(p), make_pair(s[i] % t, 0ll)) - p.begin() - 1; if (!pos) continue; if (block[pos] == -1) block[pos] = s[i] / t; } // for (int i = 1; i <= m; i++) cout<<block[i]<<" "; // cout<<endl; CHTMax cht; cht.add(0, 0); for (int i = 1; i <= m; i++) { int d = p[i].fi, c = p[i].se; dp[i] = dp[i-1] + ((x-d) / t + 1) * w; if (block[i] != -1) { // cout<<i<<" "<<pc[i] + w * block[i] * i<<" "<<-cht.query(block[i])<<endl; dp[i] = min(dp[i], -cht.query(block[i]) + pc[i] + w * block[i] * i); // cout<<i<<" "<<dp[i]<<" "<<dp[i-1] + ((x-d) / t + 1) * w<<" "<<-cht.query(block[i]) + pc[i] + w * block[i] * i<<endl; } // cout<<dp[i]<<" "; cht.add((w*i), -(dp[i] - pc[i])); } // cout<<endl; int ans = dp[m] + ((x-1) / t + 1) * w; cout<<ans; } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); solve(); }

coach.cpp: In member function 'long long int CHTMax::query(long long int)':
coach.cpp:50:45: warning: narrowing conversion of 'x' from 'long long int' to 'double' [-Wnarrowing]
   50 |         Line l = *s.lower_bound({ inf, inf, x });
      |                                             ^