#include <bits/stdc++.h>
using namespace std;
constexpr int M=500002;
struct pii {
int x, v;
bool operator<(pii b) const { return x<b.x; }
};
int main() {
ios::sync_with_stdio(0);cin.tie(0);
int N, L, R, st;
cin>>N>>L>>R>>st;
vector<pii> A[M];
for(int i=0; i<N; i++) {
int t, x, v;
cin>>t>>x>>v;
A[t].push_back({x, v});
}
auto set=[&](int* T, int i, int x) {
for(; i<M; i+=i&-i) T[i]=max(T[i], x);
};
auto qry=[&](int* T, int i) {
int x=-2e9;
for(; i; i-=i&-i) x=max(x, T[i]);
return x;
};
int T1[M], T2[M];
fill(T1, T1+M, -2e9);
fill(T2, T2+M, -2e9);
set(T1, st, st*R);
set(T2, M-st, -st*L);
for(auto&X:A) if(int n=X.size()) {
sort(X.begin(), X.end());
int D[n], E[n];
for(int i=0, m=-2e9; i<n; i++) {
auto[x,v]=X[i];
D[i]=max(qry(T1, x)-x*R, qry(T2, M-x)+x*L)+v;
E[i]=m=max(m+v, D[i]+x*R);
}
for(int i=n-1, m=-2e9; i>=0; i--) {
auto[x,v]=X[i];
m=max(m+v, D[i]-x*L);
int t=max(m+x*L, E[i]-x*R);
set(T1, x, t+x*R);
set(T2, M-x, t-x*L);
}
}
cout<<max(qry(T1, st)-st*R, qry(T2, M-st)+st*L)<<'\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
15948 KB |
Output is correct |
2 |
Correct |
12 ms |
15936 KB |
Output is correct |
3 |
Correct |
12 ms |
15948 KB |
Output is correct |
4 |
Correct |
13 ms |
16020 KB |
Output is correct |
5 |
Correct |
14 ms |
16120 KB |
Output is correct |
6 |
Correct |
31 ms |
16460 KB |
Output is correct |
7 |
Correct |
51 ms |
17432 KB |
Output is correct |
8 |
Correct |
118 ms |
19076 KB |
Output is correct |
9 |
Correct |
133 ms |
20676 KB |
Output is correct |
10 |
Correct |
237 ms |
25396 KB |
Output is correct |
11 |
Correct |
293 ms |
25340 KB |
Output is correct |
12 |
Correct |
353 ms |
28472 KB |
Output is correct |
13 |
Correct |
359 ms |
28472 KB |
Output is correct |
14 |
Correct |
444 ms |
31564 KB |
Output is correct |
15 |
Correct |
466 ms |
31600 KB |
Output is correct |
16 |
Correct |
430 ms |
31556 KB |
Output is correct |
17 |
Correct |
12 ms |
15948 KB |
Output is correct |
18 |
Correct |
12 ms |
15960 KB |
Output is correct |
19 |
Correct |
12 ms |
15964 KB |
Output is correct |
20 |
Correct |
13 ms |
15920 KB |
Output is correct |
21 |
Correct |
14 ms |
15948 KB |
Output is correct |
22 |
Correct |
16 ms |
15948 KB |
Output is correct |
23 |
Correct |
15 ms |
16056 KB |
Output is correct |
24 |
Correct |
17 ms |
16044 KB |
Output is correct |
25 |
Correct |
58 ms |
16964 KB |
Output is correct |
26 |
Correct |
106 ms |
18296 KB |
Output is correct |
27 |
Correct |
170 ms |
19912 KB |
Output is correct |
28 |
Correct |
197 ms |
20064 KB |
Output is correct |
29 |
Correct |
239 ms |
20876 KB |
Output is correct |
30 |
Correct |
254 ms |
21596 KB |
Output is correct |