#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Market{
int day; int loc; int w;
bool operator<(const Market &r)const{
return day == r.day ? loc < r.loc : day < r.day;
}
};
struct segTree{
int tree[1048578];
void init(int i, int l, int r){
if(l==r){
tree[i] = -2e9;
return;
}
int m = (l+r)>>1;
init(i*2, l, m), init(i*2+1, m+1, r);
tree[i] = -2e9;
}
void update(int i, int l, int r, int x, int v){
if(l==r){
tree[i] = max(tree[i], v);
return;
}
int m = (l+r)>>1;
if(x<=m) update(i*2, l, m, x, v);
else update(i*2+1, m+1, r, x, v);
tree[i] = max(tree[i*2], tree[i*2+1]);
}
int query(int i, int l, int r, int s, int e){
if(r<s || e<l) return -2e9;
if(s<=l && r<=e) return tree[i];
int m = (l+r)>>1;
return max(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
}
} treeU, treeD;
int n; int u, d; int s;
Market arr[500002];
int main(){
scanf("%d %d %d %d", &n, &u, &d, &s);
for(int i=1; i<=n; i++){
scanf("%d %d %d", &arr[i].day, &arr[i].loc, &arr[i].w);
}
sort(arr+1, arr+n+1);
const int MAX = 500001;
treeU.init(1, 1, MAX), treeD.init(1, 1, MAX);
treeU.update(1, 1, MAX, s, -u*s);
treeD.update(1, 1, MAX, s, d*s);
for(int i=1; i<=n; i++){
int j = i;
while(arr[j+1].day == arr[i].day) j++;
if(i==j){
int val = max(treeU.query(1, 1, MAX, arr[i].loc, MAX) + arr[i].loc * u,
treeD.query(1, 1, MAX, 1, arr[i].loc) - arr[i].loc * d) + arr[i].w;
treeU.update(1, 1, MAX, arr[i].loc, val-u*arr[i].loc);
treeD.update(1, 1, MAX, arr[i].loc, val+d*arr[i].loc);
continue;
}
vector<pair<int, int> > vec;
int btmp = -2e9;
for(int x=i; x<=j; x++){
int val = max(treeU.query(1, 1, MAX, arr[x].loc, MAX) + arr[x].loc * u,
treeD.query(1, 1, MAX, 1, arr[x].loc) - arr[x].loc * d) + arr[x].w;
val = max(val, btmp - arr[x].loc * d + arr[x].w);
vec.push_back(make_pair(arr[x].loc, val));
btmp = max(btmp, val + arr[x].loc * d);
}
for(int x=j; x>=i; x--){
int val = max(treeU.query(1, 1, MAX, arr[x].loc, MAX) + arr[x].loc * u,
treeD.query(1, 1, MAX, 1, arr[x].loc) - arr[x].loc * d) + arr[x].w;
treeU.update(1, 1, MAX, arr[x].loc, val-u*arr[x].loc);
treeD.update(1, 1, MAX, arr[x].loc, val+d*arr[x].loc);
}
for(auto p: vec){
treeU.update(1, 1, MAX, p.first, p.second-u*p.first);
treeD.update(1, 1, MAX, p.first, p.second+d*p.first);
}
i=j;
}
int ans = max(treeU.query(1, 1, MAX, s, MAX) + s*u,
treeD.query(1, 1, MAX, 1, s) - s*d);
printf("%d", ans);
}
Compilation message
salesman.cpp: In function 'int main()':
salesman.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
51 | scanf("%d %d %d %d", &n, &u, &d, &s);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
53 | scanf("%d %d %d", &arr[i].day, &arr[i].loc, &arr[i].w);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
8396 KB |
Output is correct |
2 |
Correct |
5 ms |
8396 KB |
Output is correct |
3 |
Correct |
6 ms |
8436 KB |
Output is correct |
4 |
Correct |
7 ms |
8524 KB |
Output is correct |
5 |
Correct |
13 ms |
8536 KB |
Output is correct |
6 |
Correct |
25 ms |
8732 KB |
Output is correct |
7 |
Correct |
66 ms |
8968 KB |
Output is correct |
8 |
Correct |
114 ms |
9628 KB |
Output is correct |
9 |
Correct |
182 ms |
10124 KB |
Output is correct |
10 |
Correct |
319 ms |
12124 KB |
Output is correct |
11 |
Correct |
387 ms |
11976 KB |
Output is correct |
12 |
Correct |
479 ms |
13236 KB |
Output is correct |
13 |
Correct |
438 ms |
13280 KB |
Output is correct |
14 |
Correct |
536 ms |
14276 KB |
Output is correct |
15 |
Correct |
446 ms |
14344 KB |
Output is correct |
16 |
Correct |
551 ms |
14348 KB |
Output is correct |
17 |
Correct |
6 ms |
8396 KB |
Output is correct |
18 |
Correct |
6 ms |
8396 KB |
Output is correct |
19 |
Correct |
6 ms |
8396 KB |
Output is correct |
20 |
Correct |
9 ms |
8524 KB |
Output is correct |
21 |
Correct |
8 ms |
8540 KB |
Output is correct |
22 |
Correct |
11 ms |
8560 KB |
Output is correct |
23 |
Correct |
12 ms |
8524 KB |
Output is correct |
24 |
Correct |
12 ms |
8572 KB |
Output is correct |
25 |
Correct |
155 ms |
9700 KB |
Output is correct |
26 |
Correct |
275 ms |
11172 KB |
Output is correct |
27 |
Correct |
501 ms |
17380 KB |
Output is correct |
28 |
Correct |
530 ms |
16948 KB |
Output is correct |
29 |
Correct |
702 ms |
14484 KB |
Output is correct |
30 |
Correct |
675 ms |
15524 KB |
Output is correct |