#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=500010, inf=(1<<30), XMX=500001;
const ll linf=(1LL<<60);
int n, d, u, s;
struct shop {
int t, x, a;
} S[MX];
inline ll _max(ll x, ll y){
return x<y ? y : x;
}
struct Seg {
static const int MX=(1<<20);
ll tree[MX]; int n;
void init(int sz){
n=sz;
for(int i=1; i<MX; i++) tree[i]=-linf;
}
void upt(int v, int s, int e, int pos, ll val){
if(pos<s || e<pos) return;
if(s==e){
tree[v]=val;
return;
}
int m=(s+e)>>1;
if(pos<=m) upt(v<<1,s,m,pos,val);
else upt((v<<1)+1,m+1,e,pos,val);
tree[v]=_max(tree[v<<1], tree[(v<<1)+1]);
}
void upt(int pos, ll val){
upt(1,1,n,pos,val);
}
ll mx(int v, int s, int e, int l, int r){
if(r<s || e<l) return -linf;
if(l<=s && e<=r) return tree[v];
int m=(s+e)>>1;
return _max(mx(v<<1,s,m,l,r), mx((v<<1)+1,m+1,e,l,r));
}
ll mx(int l, int r){
if(r<l) return -linf;
return mx(1,1,n,l,r);
}
} US, DS;
void upt(int pos, ll val){
US.upt(pos, val-u*pos);
DS.upt(pos, val+d*pos);
}
ll get(int x){
ll upmx=US.mx(x,XMX)+u*x, dnmx=DS.mx(1,x)-d*x;
return _max(upmx, dnmx);
}
ll T[MX];
ll X[MX], Y[MX];
void solve(int l, int r){
for(int i=l; i<=r; i++)
T[i]=get(S[i].x);
X[l]=T[l]+S[l].a;
for(int i=l+1; i<=r; i++)
X[i]=_max(X[i-1]-d*(S[i].x-S[i-1].x), T[i])+S[i].a;
Y[r]=T[r]+S[r].a;
for(int i=r-1; i>=l; i--)
Y[i]=_max(Y[i+1]-u*(S[i+1].x-S[i].x), T[i])+S[i].a;
for(int i=l; i<=r; i++)
upt(S[i].x, _max(X[i], Y[i]));
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
cin>>n>>u>>d>>s;
for(int i=1; i<=n; i++){
int t,x,a;
cin>>t>>x>>a;
S[i]={t,x,a};
}
sort(S+1, S+n+1, [](shop &a, shop &b){
if(a.t==b.t) return a.x<b.x;
return a.t<b.t;
});
DS.init(500001);
US.init(500001);
upt(s, 0);
int pos=1;
while(pos<=n){
int l=pos, r=pos;
while(r<n && S[r+1].t==S[l].t) r++;
solve(l,r);
pos=r+1;
}
cout<<get(s);
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
16760 KB |
Output is correct |
2 |
Correct |
18 ms |
16872 KB |
Output is correct |
3 |
Correct |
15 ms |
16928 KB |
Output is correct |
4 |
Correct |
20 ms |
16964 KB |
Output is correct |
5 |
Correct |
21 ms |
17060 KB |
Output is correct |
6 |
Correct |
46 ms |
17580 KB |
Output is correct |
7 |
Correct |
132 ms |
18620 KB |
Output is correct |
8 |
Correct |
193 ms |
20492 KB |
Output is correct |
9 |
Correct |
276 ms |
22236 KB |
Output is correct |
10 |
Correct |
478 ms |
27608 KB |
Output is correct |
11 |
Correct |
515 ms |
27608 KB |
Output is correct |
12 |
Correct |
730 ms |
31132 KB |
Output is correct |
13 |
Correct |
737 ms |
31248 KB |
Output is correct |
14 |
Correct |
828 ms |
34660 KB |
Output is correct |
15 |
Correct |
693 ms |
34660 KB |
Output is correct |
16 |
Correct |
845 ms |
34728 KB |
Output is correct |
17 |
Correct |
13 ms |
34728 KB |
Output is correct |
18 |
Correct |
14 ms |
34728 KB |
Output is correct |
19 |
Correct |
16 ms |
34728 KB |
Output is correct |
20 |
Correct |
19 ms |
34728 KB |
Output is correct |
21 |
Correct |
17 ms |
34728 KB |
Output is correct |
22 |
Correct |
20 ms |
34728 KB |
Output is correct |
23 |
Correct |
18 ms |
34728 KB |
Output is correct |
24 |
Correct |
18 ms |
34728 KB |
Output is correct |
25 |
Correct |
158 ms |
34728 KB |
Output is correct |
26 |
Correct |
364 ms |
34728 KB |
Output is correct |
27 |
Correct |
570 ms |
34728 KB |
Output is correct |
28 |
Correct |
562 ms |
34728 KB |
Output is correct |
29 |
Correct |
714 ms |
34728 KB |
Output is correct |
30 |
Correct |
667 ms |
34736 KB |
Output is correct |