#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> ii;
const int len = 5e5+5, mx = 5e5+1;
const ll inf = 1e17;
pair<ii, int> arr[len];
ll dp[len][2], tree[2][4*len];
void update(int p, int l, int r, int i, ll v, int t){
if (l == r)
tree[t][p] = v;
else{
int mid = (l+r)/2;
if (i <= mid)
update(2*p, l, mid, i, v, t);
else
update(2*p+1, mid+1, r, i, v, t);
tree[t][p] = max(tree[t][2*p], tree[t][2*p+1]);
}
}
ll query(int p, int l, int r, int i, int j, int t){
if (r < i || j < l)
return -inf;
if (i <= l && r <= j)
return tree[t][p];
int mid = (l+r)/2;
return max(query(2*p, l, mid, i, j, t), query(2*p+1, mid+1, r, i, j, t));
}
int main(){
int n, u, d, s;
scanf("%d %d %d %d", &n, &u, &d, &s);
for (int i = 1; i <= n; i++)
scanf("%d %d %d", &arr[i].fi.fi, &arr[i].fi.se, &arr[i].se);
arr[0] = mp(mp(0, s), 0);
arr[n+1] = mp(mp(len, s), 0);
sort(arr+1, arr+n+1);
for (int i = 0; i < 4*mx; i++)
tree[0][i] = tree[1][i] = -inf;
update(1, 0, mx, s, +s*u, 0);
update(1, 0, mx, s, -s*d, 1);
for (int i = n, j = n+1; i >= 0; i--, j--){
while (i-1 >= 0 && arr[i-1].fi.fi == arr[i].fi.fi)
i--;
while (j-1 >= 0 && arr[j-1].fi.fi == arr[j].fi.fi)
j--;
for (int k = i; k < j; k++){
dp[k][1] = dp[k][0] = max(query(1, 0, mx, 0, arr[k].fi.se, 0)-u*arr[k].fi.se, query(1, 0, mx, arr[k].fi.se, mx, 1)+arr[k].fi.se*d);
if (k != i)
dp[k][0] = max(dp[k][0], dp[k-1][0] - (arr[k].fi.se-arr[k-1].fi.se)*u + arr[k-1].se);
}
for (int k = j-1; k >= i; k--){
if (k != j-1)
dp[k][1] = max(dp[k][1], dp[k+1][1] - (arr[k+1].fi.se-arr[k].fi.se)*d + arr[k+1].se);
}
for (int k = i; k < j; k++){
update(1, 0, mx, arr[k].fi.se, max(dp[k][0], dp[k][1])+arr[k].se+arr[k].fi.se*u, 0);
update(1, 0, mx, arr[k].fi.se, max(dp[k][0], dp[k][1])+arr[k].se-arr[k].fi.se*d, 1);
}
}
printf("%lld\n", dp[0][0]);
return 0;
}
Compilation message
salesman.cpp: In function 'int main()':
salesman.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d", &n, &u, &d, &s);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:44:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &arr[i].fi.fi, &arr[i].fi.se, &arr[i].se);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
31736 KB |
Output is correct |
2 |
Correct |
25 ms |
31616 KB |
Output is correct |
3 |
Correct |
25 ms |
31736 KB |
Output is correct |
4 |
Correct |
27 ms |
31736 KB |
Output is correct |
5 |
Correct |
30 ms |
31736 KB |
Output is correct |
6 |
Correct |
59 ms |
32248 KB |
Output is correct |
7 |
Correct |
114 ms |
33016 KB |
Output is correct |
8 |
Correct |
204 ms |
34392 KB |
Output is correct |
9 |
Correct |
285 ms |
35832 KB |
Output is correct |
10 |
Correct |
571 ms |
39900 KB |
Output is correct |
11 |
Correct |
574 ms |
40056 KB |
Output is correct |
12 |
Correct |
738 ms |
42764 KB |
Output is correct |
13 |
Correct |
750 ms |
42772 KB |
Output is correct |
14 |
Correct |
907 ms |
45304 KB |
Output is correct |
15 |
Correct |
768 ms |
45432 KB |
Output is correct |
16 |
Correct |
968 ms |
45432 KB |
Output is correct |
17 |
Correct |
26 ms |
31608 KB |
Output is correct |
18 |
Correct |
26 ms |
31744 KB |
Output is correct |
19 |
Correct |
27 ms |
31616 KB |
Output is correct |
20 |
Correct |
29 ms |
31744 KB |
Output is correct |
21 |
Correct |
28 ms |
31744 KB |
Output is correct |
22 |
Correct |
34 ms |
31864 KB |
Output is correct |
23 |
Correct |
26 ms |
31864 KB |
Output is correct |
24 |
Correct |
30 ms |
31736 KB |
Output is correct |
25 |
Correct |
180 ms |
34324 KB |
Output is correct |
26 |
Correct |
333 ms |
37168 KB |
Output is correct |
27 |
Correct |
520 ms |
41236 KB |
Output is correct |
28 |
Correct |
575 ms |
41192 KB |
Output is correct |
29 |
Correct |
828 ms |
45392 KB |
Output is correct |
30 |
Correct |
734 ms |
45448 KB |
Output is correct |