#include "bits/stdc++.h"
using namespace std;
#define ar array
//~ #define double long double
using ll = long long;
const long long inf = 1e18;
const int N = 2e5 + 5;
struct node{
long long m, b;
int lx, rx;
double operator * (node& x){
return (x.b - b) * 1. / (m - x.m);
}
ll cost(int x){
return m * x + b;
}
};
const long long M = 1e12 + 5;
int t, w;
struct LiChao{
node tree[N * 30] {};
int last;
void init(){
for(int i=0;i<N*30;i++) tree[i] = {w * t, inf, 0, 0};
last = 0;
}
void make(int x){
if(!tree[x].lx) tree[x].lx = ++last;
if(!tree[x].rx) tree[x].rx = ++last;
}
void add(node v, long long lx = 0, long long rx = M, int x = 0){
if(tree[x].m == v.m){
tree[x].b = min(v.b, tree[x].b);
return;
}
if(lx == rx){
if(tree[x].cost(lx) > v.cost(lx)) swap(tree[x], v);
return;
}
make(x);
double in = tree[x] * v;
long long m = (lx + rx) >> 1;
v.lx = tree[x].lx, v.rx = tree[x].rx;
if(m < in){
if(tree[x].cost(m) > v.cost(m)){
swap(tree[x], v);
}
add(v, m + 1, rx, tree[x].rx);
} else {
if(tree[x].cost(m + 1) > v.cost(m + 1)){
swap(tree[x], v);
}
add(v, lx, m, tree[x].lx);
}
}
long long get(long long i, long long lx = 0, long long rx = M, int x = 0){
if(lx == rx) return tree[x].cost(i);
int m = (lx + rx) >> 1;
make(x);
if(i <= m) return min(get(i, lx, m, tree[x].lx), tree[x].cost(i));
else return min(get(i, m+1, rx, tree[x].rx), tree[x].cost(i));
}
}tree;
ll s[N], d[N], c[N], pref[N], cnt[N];
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int x, n, m; cin>>x>>n>>m>>w>>t;
tree.init();
for(int i=0;i<n;i++) cin>>s[i];
vector<ll> p(m), d_(m), mn(m, x + 1);
ll tot = 0;
for(int i=0;i<m;i++){
cin>>d[i]>>c[i];
p[i] = i;
}
tot += (x / t + 1) * w;
sort(p.begin(), p.end(), [&](int i, int j){
return d[i] < d[j];
});
for(int i=0;i<m;i++){
d_[i] = d[p[i]];
cnt[i] = x / t + (d_[i] < x % t);
tot += cnt[i] * w;
if(i) pref[i] += pref[i-1], cnt[i] += cnt[i-1];
pref[i] += c[p[i]];
}
s[n] = x;
for(int i=0;i<=n;i++){
int j = upper_bound(d_.begin(), d_.end(), s[i] % t) - d_.begin();
if(j){ --j;
//~ assert(d_[j] != s[i] % t);
mn[j] = min(mn[j], s[i]);
}
}
//~ cout<<w<<"\n";
//~ for(int i=0;i<m;i++){
//~ cout<<-i * w<<" "<<cnt[i] * w - pref[i]<<"\n";
//~ }
vector<ll> dp(m);
ll Mx = M / t + 5;
tree.add({w, 0});
for(int i=0;i<m;i++){
if(i) dp[i] = dp[i-1];
if(mn[i] > x){
tree.add({-i * w, dp[i] + cnt[i] * w - pref[i]}, 0, Mx);
continue;
}
ll T = mn[i] / t;
dp[i] = min(dp[i], tree.get(T, 0, Mx) - cnt[i] * w + T * i * w + pref[i]);
tree.add({-i * w, dp[i] + cnt[i] * w - pref[i]}, 0, Mx);
}
//~ for(int i=0;i<m;i++) cout<<dp[i]<<" ";
//~ cout<<"\n";
cout<<tot + dp[m-1]<<"\n";
}
/*
0 0 0 0 -23
0 0 0 0 -29
105 3 5 9 10
59
68
71
4 71
6 32
7 29
3 62
2 35
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
195 ms |
262144 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
195 ms |
262144 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
195 ms |
262144 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
195 ms |
262144 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
