#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=500005,inf=500001;
struct seg
{
int tr[N<<3];
void build(int k,int l,int r)
{
tr[k]=-1e18;
if(l==r)
return;
int mid=l+r>>1;
build(k<<1,l,mid);
build(k<<1|1,mid+1,r);
}
void update(int k,int l,int r,int x,int v)
{
if(l==r)
{
tr[k]=v;
return;
}
int mid=l+r>>1;
if(x<=mid) update(k<<1,l,mid,x,v);
else update(k<<1|1,mid+1,r,x,v);
tr[k]=max(tr[k<<1],tr[k<<1|1]);
}
int query(int k,int l,int r,int a,int b)
{
if(l==a&&r==b)
return tr[k];
int mid=l+r>>1;
if(b<=mid) return query(k<<1,l,mid,a,b);
else if(a>mid) return query(k<<1|1,mid+1,r,a,b);
else return max(query(k<<1,l,mid,a,mid),query(k<<1|1,mid+1,r,mid+1,b));
}
}s1,s2;
int n,u,d,s,ans;
vector<pair<int,int>>a[N];
signed main()
{
ios::sync_with_stdio(false);
cin>>n>>u>>d>>s;
for(int i=1;i<=n;i++)
{
int t,l,w;
cin>>t>>l>>w;
a[t].emplace_back(l,w);
}
s1.build(1,1,inf);
s2.build(1,1,inf);
s1.update(1,1,inf,s,d*s);
s2.update(1,1,inf,s,-u*s);
for(int i=1;i<=inf;i++)
{
if(a[i].size()==0)
continue;
sort(a[i].begin(),a[i].end());
int m=a[i].size(),t;
vector<int>b(m),y(m),z(m);
for(int j=0;j<m;j++)
{
int x=a[i][j].first,w=a[i][j].second;
b[j]=max(s1.query(1,1,inf,1,x)-x*d,s2.query(1,1,inf,x,inf)+x*u)+w;
}
t=b[0];
for(int j=0;j<m;j++)
{
int x=a[i][j].first,w=a[i][j].second;
if(j) t=max(t-(x-a[i][j-1].first)*d+w,b[j]);
y[j]=t;
}
t=b[m-1];
for(int j=m-1;j>=0;j--)
{
int x=a[i][j].first,w=a[i][j].second;
if(j!=m-1) t=max(t-(a[i][j+1].first-x)*u+w,b[j]);
z[j]=t;
}
for(int j=0;j<m;j++)
{
b[j]=max(y[j],z[j]);
int x=a[i][j].first;
s1.update(1,1,inf,x,b[j]+d*x);
s2.update(1,1,inf,x,b[j]-u*x);
ans=max(ans,b[j]-(x>s?u*(x-s):d*(s-x)));
}
}
cout<<ans<<endl;
return 0;
}
Compilation message
salesman.cpp: In member function 'void seg::build(long long int, long long int, long long int)':
salesman.cpp:13:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
13 | int mid=l+r>>1;
| ~^~
salesman.cpp: In member function 'void seg::update(long long int, long long int, long long int, long long int, long long int)':
salesman.cpp:24:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
24 | int mid=l+r>>1;
| ~^~
salesman.cpp: In member function 'long long int seg::query(long long int, long long int, long long int, long long int, long long int)':
salesman.cpp:33:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
33 | int mid=l+r>>1;
| ~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
28524 KB |
Output is correct |
2 |
Correct |
23 ms |
28524 KB |
Output is correct |
3 |
Correct |
24 ms |
28524 KB |
Output is correct |
4 |
Correct |
25 ms |
28524 KB |
Output is correct |
5 |
Correct |
28 ms |
28652 KB |
Output is correct |
6 |
Correct |
59 ms |
29164 KB |
Output is correct |
7 |
Correct |
120 ms |
30060 KB |
Output is correct |
8 |
Correct |
212 ms |
31724 KB |
Output is correct |
9 |
Correct |
302 ms |
33356 KB |
Output is correct |
10 |
Correct |
493 ms |
38016 KB |
Output is correct |
11 |
Correct |
611 ms |
37960 KB |
Output is correct |
12 |
Correct |
779 ms |
41196 KB |
Output is correct |
13 |
Correct |
783 ms |
41068 KB |
Output is correct |
14 |
Correct |
964 ms |
44272 KB |
Output is correct |
15 |
Correct |
815 ms |
44220 KB |
Output is correct |
16 |
Correct |
981 ms |
44140 KB |
Output is correct |
17 |
Correct |
23 ms |
28524 KB |
Output is correct |
18 |
Correct |
24 ms |
28524 KB |
Output is correct |
19 |
Correct |
24 ms |
28524 KB |
Output is correct |
20 |
Correct |
25 ms |
28652 KB |
Output is correct |
21 |
Correct |
26 ms |
28524 KB |
Output is correct |
22 |
Correct |
28 ms |
28652 KB |
Output is correct |
23 |
Correct |
27 ms |
28652 KB |
Output is correct |
24 |
Correct |
28 ms |
28652 KB |
Output is correct |
25 |
Correct |
151 ms |
30828 KB |
Output is correct |
26 |
Correct |
287 ms |
33376 KB |
Output is correct |
27 |
Correct |
419 ms |
36944 KB |
Output is correct |
28 |
Correct |
518 ms |
36700 KB |
Output is correct |
29 |
Correct |
646 ms |
37740 KB |
Output is correct |
30 |
Correct |
615 ms |
40544 KB |
Output is correct |