#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<ll,ll>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=5e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
struct node
{
ll be ,lon;
node ()
{
be=-inf;
lon=-inf;
}
node operator+(const node&o)
{
node ans;
ans.be=max(be,o.be);
ans.lon=max(lon,o.lon);
return ans;
}
}st[4*maxN];
ll o,u,d;
void update(ll pos,ll val,ll id=1,ll l=1,ll r=o)
{
if(l==r)
{
st[id].lon=val-pos*u;
st[id].be=val+pos*d;
return;
}
ll mid=l+r>>1;
if(pos<=mid) update(pos,val,id*2,l,mid);
else update(pos,val,id*2+1,mid+1,r);
st[id]=st[id*2]+st[id*2+1];
}
node get(ll i,ll j,ll id=1,ll l=1,ll r=o)
{
if(j<l||r<i) return node();
if(i<=l&&r<=j) return st[id];
ll mid=l+r>>1;
return get(i,j,id*2,l,mid)+get(i,j,id*2+1,mid+1,r);
}
ll n,s;
struct qq
{
ll t,l,m;
bool operator<(const qq&o)
{
return t<o.t;
}
}e[maxN];
pli a[maxN];
ll val[maxN],pre[maxN],luu[maxN];
void solve()
{
cin >> n >> u >> d >> s;
o=s;
for(int i=1;i<=n;i++)
{
cin >> e[i].t >> e[i].l >> e[i].m;
o=max(o,e[i].l);
}
n++;
e[n].t=inf;
e[n].l=s;
e[n].m=0;
n--;
sort(e+1,e+n+1);
ll ans=0;
update(s,0);
for(int i=1;i<=n;i++)
{
ll j=i;
while(j<=n&&e[j].t==e[i].t)
{
a[j-i+1]={e[j].l,e[j].m};
j++;
}
sort(a+1,a+j-i+1);
for(int k=1;k<=j-i;k++)
{
val[k]=max(get(a[k].fi+1,o).lon+a[k].fi*u+a[k].se,get(1,a[k].fi-1).be-a[k].fi*d+a[k].se);
val[k]=max(val[k],-inf);
pre[k]=pre[k-1]+a[k].se;
luu[k]=val[k];
}
ll mx=-inf;
for(int k=2;k<=j-i;k++)
{
mx=max(mx,val[k-1]-pre[k-1]+a[k-1].fi*d);
luu[k]=max(luu[k],pre[k]-a[k].fi*d+mx);
}
mx=-inf;
for(int k=j-i-1;k>=1;k--)
{
ll vv=k+1;
mx=max(mx,val[vv]+pre[vv-1]-a[vv].fi*u);
luu[k]=max(luu[k],-pre[k-1]+a[k].fi*u+mx);
}
for(int k=1;k<=j-i;k++)
{
if(a[k].fi<s) ans=max(ans,luu[k]-d*(s-a[k].fi));
else ans=max(ans,luu[k]+-u*(a[k].fi-s));
update(a[k].fi,luu[k]);
}
i=j-1;
}
cout << ans;
}
int main()
{
fastio
//freopen(TASKNAME".INP","r",stdin);
//freopen(TASKNAME".OUT","w",stdout);
solve();
}
Compilation message
salesman.cpp: In function 'void update(ll, ll, ll, ll, ll)':
salesman.cpp:38:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
38 | ll mid=l+r>>1;
| ~^~
salesman.cpp: In function 'node get(ll, ll, ll, ll, ll)':
salesman.cpp:47:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
47 | ll mid=l+r>>1;
| ~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
31572 KB |
Output is correct |
2 |
Correct |
13 ms |
31552 KB |
Output is correct |
3 |
Correct |
14 ms |
31688 KB |
Output is correct |
4 |
Correct |
16 ms |
31680 KB |
Output is correct |
5 |
Correct |
17 ms |
31712 KB |
Output is correct |
6 |
Correct |
35 ms |
32192 KB |
Output is correct |
7 |
Correct |
68 ms |
32768 KB |
Output is correct |
8 |
Correct |
114 ms |
34000 KB |
Output is correct |
9 |
Correct |
163 ms |
35132 KB |
Output is correct |
10 |
Correct |
273 ms |
38696 KB |
Output is correct |
11 |
Correct |
324 ms |
38600 KB |
Output is correct |
12 |
Correct |
394 ms |
40988 KB |
Output is correct |
13 |
Correct |
411 ms |
41036 KB |
Output is correct |
14 |
Correct |
503 ms |
43384 KB |
Output is correct |
15 |
Correct |
443 ms |
43484 KB |
Output is correct |
16 |
Correct |
519 ms |
43552 KB |
Output is correct |
17 |
Correct |
13 ms |
31624 KB |
Output is correct |
18 |
Correct |
14 ms |
31680 KB |
Output is correct |
19 |
Correct |
14 ms |
31680 KB |
Output is correct |
20 |
Correct |
15 ms |
31652 KB |
Output is correct |
21 |
Correct |
15 ms |
31712 KB |
Output is correct |
22 |
Correct |
16 ms |
31700 KB |
Output is correct |
23 |
Correct |
17 ms |
31740 KB |
Output is correct |
24 |
Correct |
17 ms |
31696 KB |
Output is correct |
25 |
Correct |
109 ms |
34252 KB |
Output is correct |
26 |
Correct |
192 ms |
37496 KB |
Output is correct |
27 |
Correct |
314 ms |
42464 KB |
Output is correct |
28 |
Correct |
347 ms |
41172 KB |
Output is correct |
29 |
Correct |
439 ms |
43700 KB |
Output is correct |
30 |
Correct |
453 ms |
46544 KB |
Output is correct |