#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(_a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(_a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <int,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"
using namespace std;
const int N = 5e5 + 5;
const ll oo = 1e18;
const ll mod = 1e9 + 7;
bool flag;
struct line {
mutable ll k,m,p;
bool operator < (const line&u) const {
return flag ? p < u.p : k < u.k;
}
};
struct linecontainer : multiset <line> {
ll fdiv (ll a, ll b){
return a / b - ((a ^ b) < 0 && a % b);
}
bool its (iterator x, iterator y){
if (y == end()) return x -> p = oo,0;
if (y -> k == x -> k) x -> p = x -> m > y -> m ? oo : -oo;
else x -> p = fdiv (x -> m - y -> m, y -> k - x -> k);
return x -> p >= y -> p;
}
void add (ll k, ll m){
auto z = insert({k,m,0}),y = z++, x = y;
while (its(y,z)) z = erase(z);
if (x != begin() && its(--x,y)) y = erase(y);
while ((y = x) != begin() && (--x) -> p >= y -> p) its(x,y = erase(y));
}
ll query(ll x){
if (empty()) return -oo;
flag = 1;
line l = *lower_bound({0,0,x});
flag = 0;
return l.k * x + l.m;
}
};
ll x,n,m,w,t,s[N],i,sum,refd[N],dp[N];
pll f[N];
linecontainer lc;
vector <ll> ev[N];
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> x >> n >> m >> w >> t;
x--;
forr (i,1,n)
cin >> s[i];
forr (i,1,m){
cin >> f[i].st >> f[i].nd;
if (f[i].st <= x % t)
f[i].nd -= w,sum += w;
}
n++;
s[n] = x;
sort(f + 1, f + 1 + m);
ll lmt = x / t;
sum += lmt * (m + 1) * w + w;
forr (i,1,n){
int k = upper_bound (f + 1, f + 1 + m, mp(s[i] % t,0ll)) - f - 1;
if (k == 0)
continue;
ev[k].pb(lmt - s[i] / t);
}
forr (i,1,m)
refd[i] = refd[i - 1] + f[i].nd;
//cout << lmt << " " << sum << "\n";
ll ans = 0;
ford (i,m,1){
dp[i] = dp[i + 1];
for (ll u : ev[i])
lc.add(w * u, dp[i] + (i + 1) * u * w - refd[i]);
ll tmp = lc.query(-i) + refd[i - 1];
dp[i] = max (dp[i],tmp);
ans = max (ans,dp[i]);
// cout << dp[i] << " " << refd[i] << " " << f[i].nd << "\n";
}
cout << sum - ans;
return 0;
}
/*
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
14940 KB |
Output is correct |
2 |
Correct |
3 ms |
14940 KB |
Output is correct |
3 |
Correct |
3 ms |
15016 KB |
Output is correct |
4 |
Correct |
3 ms |
14940 KB |
Output is correct |
5 |
Correct |
4 ms |
14940 KB |
Output is correct |
6 |
Correct |
3 ms |
14940 KB |
Output is correct |
7 |
Correct |
3 ms |
14940 KB |
Output is correct |
8 |
Correct |
3 ms |
14940 KB |
Output is correct |
9 |
Correct |
3 ms |
14940 KB |
Output is correct |
10 |
Correct |
3 ms |
14940 KB |
Output is correct |
11 |
Correct |
3 ms |
14940 KB |
Output is correct |
12 |
Correct |
3 ms |
14940 KB |
Output is correct |
13 |
Correct |
3 ms |
14940 KB |
Output is correct |
14 |
Correct |
3 ms |
14940 KB |
Output is correct |
15 |
Correct |
4 ms |
14940 KB |
Output is correct |
16 |
Correct |
4 ms |
14940 KB |
Output is correct |
17 |
Correct |
3 ms |
14940 KB |
Output is correct |
18 |
Correct |
3 ms |
14940 KB |
Output is correct |
19 |
Correct |
3 ms |
14940 KB |
Output is correct |
20 |
Correct |
3 ms |
14940 KB |
Output is correct |
21 |
Correct |
3 ms |
14940 KB |
Output is correct |
22 |
Correct |
3 ms |
15020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
14940 KB |
Output is correct |
2 |
Correct |
3 ms |
14940 KB |
Output is correct |
3 |
Correct |
3 ms |
15016 KB |
Output is correct |
4 |
Correct |
3 ms |
14940 KB |
Output is correct |
5 |
Correct |
4 ms |
14940 KB |
Output is correct |
6 |
Correct |
3 ms |
14940 KB |
Output is correct |
7 |
Correct |
3 ms |
14940 KB |
Output is correct |
8 |
Correct |
3 ms |
14940 KB |
Output is correct |
9 |
Correct |
3 ms |
14940 KB |
Output is correct |
10 |
Correct |
3 ms |
14940 KB |
Output is correct |
11 |
Correct |
3 ms |
14940 KB |
Output is correct |
12 |
Correct |
3 ms |
14940 KB |
Output is correct |
13 |
Correct |
3 ms |
14940 KB |
Output is correct |
14 |
Correct |
3 ms |
14940 KB |
Output is correct |
15 |
Correct |
4 ms |
14940 KB |
Output is correct |
16 |
Correct |
4 ms |
14940 KB |
Output is correct |
17 |
Correct |
3 ms |
14940 KB |
Output is correct |
18 |
Correct |
3 ms |
14940 KB |
Output is correct |
19 |
Correct |
3 ms |
14940 KB |
Output is correct |
20 |
Correct |
3 ms |
14940 KB |
Output is correct |
21 |
Correct |
3 ms |
14940 KB |
Output is correct |
22 |
Correct |
3 ms |
15020 KB |
Output is correct |
23 |
Correct |
3 ms |
14940 KB |
Output is correct |
24 |
Correct |
3 ms |
14940 KB |
Output is correct |
25 |
Correct |
3 ms |
14940 KB |
Output is correct |
26 |
Correct |
3 ms |
14940 KB |
Output is correct |
27 |
Correct |
3 ms |
14940 KB |
Output is correct |
28 |
Correct |
3 ms |
14996 KB |
Output is correct |
29 |
Correct |
3 ms |
14940 KB |
Output is correct |
30 |
Correct |
3 ms |
14940 KB |
Output is correct |
31 |
Correct |
3 ms |
14940 KB |
Output is correct |
32 |
Correct |
3 ms |
14936 KB |
Output is correct |
33 |
Correct |
3 ms |
14936 KB |
Output is correct |
34 |
Correct |
3 ms |
14940 KB |
Output is correct |
35 |
Correct |
3 ms |
14940 KB |
Output is correct |
36 |
Correct |
3 ms |
14940 KB |
Output is correct |
37 |
Correct |
3 ms |
14940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
14940 KB |
Output is correct |
2 |
Correct |
3 ms |
14940 KB |
Output is correct |
3 |
Correct |
3 ms |
15016 KB |
Output is correct |
4 |
Correct |
3 ms |
14940 KB |
Output is correct |
5 |
Correct |
4 ms |
14940 KB |
Output is correct |
6 |
Correct |
3 ms |
14940 KB |
Output is correct |
7 |
Correct |
3 ms |
14940 KB |
Output is correct |
8 |
Correct |
3 ms |
14940 KB |
Output is correct |
9 |
Correct |
3 ms |
14940 KB |
Output is correct |
10 |
Correct |
3 ms |
14940 KB |
Output is correct |
11 |
Correct |
3 ms |
14940 KB |
Output is correct |
12 |
Correct |
3 ms |
14940 KB |
Output is correct |
13 |
Correct |
3 ms |
14940 KB |
Output is correct |
14 |
Correct |
3 ms |
14940 KB |
Output is correct |
15 |
Correct |
4 ms |
14940 KB |
Output is correct |
16 |
Correct |
4 ms |
14940 KB |
Output is correct |
17 |
Correct |
3 ms |
14940 KB |
Output is correct |
18 |
Correct |
3 ms |
14940 KB |
Output is correct |
19 |
Correct |
3 ms |
14940 KB |
Output is correct |
20 |
Correct |
3 ms |
14940 KB |
Output is correct |
21 |
Correct |
3 ms |
14940 KB |
Output is correct |
22 |
Correct |
3 ms |
15020 KB |
Output is correct |
23 |
Correct |
3 ms |
14940 KB |
Output is correct |
24 |
Correct |
3 ms |
14940 KB |
Output is correct |
25 |
Correct |
3 ms |
14940 KB |
Output is correct |
26 |
Correct |
3 ms |
14940 KB |
Output is correct |
27 |
Correct |
3 ms |
14940 KB |
Output is correct |
28 |
Correct |
3 ms |
14996 KB |
Output is correct |
29 |
Correct |
3 ms |
14940 KB |
Output is correct |
30 |
Correct |
3 ms |
14940 KB |
Output is correct |
31 |
Correct |
3 ms |
14940 KB |
Output is correct |
32 |
Correct |
3 ms |
14936 KB |
Output is correct |
33 |
Correct |
3 ms |
14936 KB |
Output is correct |
34 |
Correct |
3 ms |
14940 KB |
Output is correct |
35 |
Correct |
3 ms |
14940 KB |
Output is correct |
36 |
Correct |
3 ms |
14940 KB |
Output is correct |
37 |
Correct |
3 ms |
14940 KB |
Output is correct |
38 |
Correct |
4 ms |
14936 KB |
Output is correct |
39 |
Correct |
3 ms |
14940 KB |
Output is correct |
40 |
Correct |
4 ms |
15060 KB |
Output is correct |
41 |
Correct |
4 ms |
14940 KB |
Output is correct |
42 |
Correct |
4 ms |
14956 KB |
Output is correct |
43 |
Correct |
4 ms |
14936 KB |
Output is correct |
44 |
Correct |
4 ms |
14940 KB |
Output is correct |
45 |
Correct |
4 ms |
15132 KB |
Output is correct |
46 |
Correct |
4 ms |
15196 KB |
Output is correct |
47 |
Correct |
4 ms |
14940 KB |
Output is correct |
48 |
Correct |
4 ms |
14940 KB |
Output is correct |
49 |
Correct |
5 ms |
15056 KB |
Output is correct |
50 |
Correct |
4 ms |
14936 KB |
Output is correct |
51 |
Correct |
5 ms |
14936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
14940 KB |
Output is correct |
2 |
Correct |
3 ms |
14940 KB |
Output is correct |
3 |
Correct |
3 ms |
15016 KB |
Output is correct |
4 |
Correct |
3 ms |
14940 KB |
Output is correct |
5 |
Correct |
4 ms |
14940 KB |
Output is correct |
6 |
Correct |
3 ms |
14940 KB |
Output is correct |
7 |
Correct |
3 ms |
14940 KB |
Output is correct |
8 |
Correct |
3 ms |
14940 KB |
Output is correct |
9 |
Correct |
3 ms |
14940 KB |
Output is correct |
10 |
Correct |
3 ms |
14940 KB |
Output is correct |
11 |
Correct |
3 ms |
14940 KB |
Output is correct |
12 |
Correct |
3 ms |
14940 KB |
Output is correct |
13 |
Correct |
3 ms |
14940 KB |
Output is correct |
14 |
Correct |
3 ms |
14940 KB |
Output is correct |
15 |
Correct |
4 ms |
14940 KB |
Output is correct |
16 |
Correct |
4 ms |
14940 KB |
Output is correct |
17 |
Correct |
3 ms |
14940 KB |
Output is correct |
18 |
Correct |
3 ms |
14940 KB |
Output is correct |
19 |
Correct |
3 ms |
14940 KB |
Output is correct |
20 |
Correct |
3 ms |
14940 KB |
Output is correct |
21 |
Correct |
3 ms |
14940 KB |
Output is correct |
22 |
Correct |
3 ms |
15020 KB |
Output is correct |
23 |
Correct |
3 ms |
14940 KB |
Output is correct |
24 |
Correct |
3 ms |
14940 KB |
Output is correct |
25 |
Correct |
3 ms |
14940 KB |
Output is correct |
26 |
Correct |
3 ms |
14940 KB |
Output is correct |
27 |
Correct |
3 ms |
14940 KB |
Output is correct |
28 |
Correct |
3 ms |
14996 KB |
Output is correct |
29 |
Correct |
3 ms |
14940 KB |
Output is correct |
30 |
Correct |
3 ms |
14940 KB |
Output is correct |
31 |
Correct |
3 ms |
14940 KB |
Output is correct |
32 |
Correct |
3 ms |
14936 KB |
Output is correct |
33 |
Correct |
3 ms |
14936 KB |
Output is correct |
34 |
Correct |
3 ms |
14940 KB |
Output is correct |
35 |
Correct |
3 ms |
14940 KB |
Output is correct |
36 |
Correct |
3 ms |
14940 KB |
Output is correct |
37 |
Correct |
3 ms |
14940 KB |
Output is correct |
38 |
Correct |
4 ms |
14936 KB |
Output is correct |
39 |
Correct |
3 ms |
14940 KB |
Output is correct |
40 |
Correct |
4 ms |
15060 KB |
Output is correct |
41 |
Correct |
4 ms |
14940 KB |
Output is correct |
42 |
Correct |
4 ms |
14956 KB |
Output is correct |
43 |
Correct |
4 ms |
14936 KB |
Output is correct |
44 |
Correct |
4 ms |
14940 KB |
Output is correct |
45 |
Correct |
4 ms |
15132 KB |
Output is correct |
46 |
Correct |
4 ms |
15196 KB |
Output is correct |
47 |
Correct |
4 ms |
14940 KB |
Output is correct |
48 |
Correct |
4 ms |
14940 KB |
Output is correct |
49 |
Correct |
5 ms |
15056 KB |
Output is correct |
50 |
Correct |
4 ms |
14936 KB |
Output is correct |
51 |
Correct |
5 ms |
14936 KB |
Output is correct |
52 |
Correct |
124 ms |
36300 KB |
Output is correct |
53 |
Correct |
83 ms |
38992 KB |
Output is correct |
54 |
Correct |
134 ms |
35668 KB |
Output is correct |
55 |
Correct |
135 ms |
35864 KB |
Output is correct |
56 |
Correct |
140 ms |
36008 KB |
Output is correct |
57 |
Correct |
155 ms |
35700 KB |
Output is correct |
58 |
Correct |
123 ms |
36360 KB |
Output is correct |
59 |
Correct |
121 ms |
35664 KB |
Output is correct |
60 |
Correct |
123 ms |
35672 KB |
Output is correct |
61 |
Correct |
120 ms |
35696 KB |
Output is correct |
62 |
Correct |
123 ms |
35836 KB |
Output is correct |
63 |
Correct |
116 ms |
43376 KB |
Output is correct |
64 |
Correct |
60 ms |
32644 KB |
Output is correct |
65 |
Correct |
87 ms |
38996 KB |
Output is correct |
66 |
Correct |
96 ms |
39300 KB |
Output is correct |
67 |
Correct |
86 ms |
38912 KB |
Output is correct |
68 |
Correct |
83 ms |
38996 KB |
Output is correct |
69 |
Correct |
122 ms |
36184 KB |
Output is correct |
70 |
Correct |
133 ms |
36104 KB |
Output is correct |
71 |
Correct |
130 ms |
36232 KB |
Output is correct |
72 |
Correct |
126 ms |
36228 KB |
Output is correct |
73 |
Correct |
136 ms |
36108 KB |
Output is correct |
74 |
Correct |
142 ms |
36176 KB |
Output is correct |
75 |
Correct |
140 ms |
36272 KB |
Output is correct |
76 |
Correct |
133 ms |
36432 KB |
Output is correct |
77 |
Correct |
131 ms |
36160 KB |
Output is correct |
78 |
Correct |
117 ms |
36284 KB |
Output is correct |
79 |
Correct |
135 ms |
36096 KB |
Output is correct |
80 |
Correct |
129 ms |
35700 KB |
Output is correct |