#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=500001;
int mvl,mvr;
int tlee[4*N]; //left endpoint
int tree[4*N]; //right endpoint
array<int,3> fairs[N];
int best[N];
void update(int idx,int l,int r,int pos,int val)
{
if(l==r)
{
tlee[idx]=val-mvr*l;
tree[idx]=val+mvl*l;
}
else
{
int m=(l+r)/2;
if(pos<=m) update(2*idx,l,m,pos,val);
else update(2*idx+1,m+1,r,pos,val);
tlee[idx]=max(tlee[2*idx],tlee[2*idx+1]);
tree[idx]=max(tree[2*idx],tree[2*idx+1]);
}
}
int query(int idx,int l,int r,int ql,int qr,int t)
{
if(ql>qr) return -(1<<30);
if(l==ql&&r==qr) return (t==0?tlee[idx]:tree[idx]);
int m=(l+r)/2;
return max(query(2*idx,l,m,ql,min(qr,m),t),query(2*idx+1,m+1,r,max(ql,m+1),qr,t));
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
memset(tlee,128,sizeof(tlee));
memset(tree,128,sizeof(tree));
memset(best,128,sizeof(best));
int n,s;
cin >> n >> mvl >> mvr >> s;
mvl=-mvl; mvr=-mvr;
for(int i=0;i<n;i++) for(int j=0;j<3;j++) cin >> fairs[i][j];
sort(fairs,fairs+n);
update(1,1,N,s,0);
auto getopt=[&](int p)->int
{
return max(query(1,1,N,1,p,0)+mvr*p,query(1,1,N,p,N,1)-mvl*p);
};
auto chmax=[&](int &a,int b){a=max(a,b);};
int tl=0;
while(tl<n)
{
int tr=tl;
while(tr+1<n&&fairs[tr+1][0]==fairs[tl][0]) tr++;
int opt=-(1<<30);
for(int i=tl;i<=tr;i++)
{
auto [t,p,c]=fairs[i];
int now=max(getopt(p),opt+mvr*p)+c;
chmax(best[i],now);
chmax(opt,now-mvr*p);
}
opt=-(1<<30);
for(int i=tr;i>=tl;i--)
{
auto [t,p,c]=fairs[i];
int now=max(getopt(p),opt-mvl*p)+c;
chmax(best[i],now);
chmax(opt,now+mvl*p);
}
for(int i=tl;i<=tr;i++) update(1,1,N,fairs[i][1],best[i]);
tl=tr+1;
}
cout << getopt(s) << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
17876 KB |
Output is correct |
2 |
Correct |
8 ms |
17876 KB |
Output is correct |
3 |
Correct |
8 ms |
17952 KB |
Output is correct |
4 |
Correct |
9 ms |
17876 KB |
Output is correct |
5 |
Correct |
13 ms |
18008 KB |
Output is correct |
6 |
Correct |
32 ms |
18132 KB |
Output is correct |
7 |
Correct |
72 ms |
18516 KB |
Output is correct |
8 |
Correct |
139 ms |
19148 KB |
Output is correct |
9 |
Correct |
186 ms |
19660 KB |
Output is correct |
10 |
Correct |
333 ms |
21380 KB |
Output is correct |
11 |
Correct |
398 ms |
21452 KB |
Output is correct |
12 |
Correct |
498 ms |
22600 KB |
Output is correct |
13 |
Correct |
510 ms |
22752 KB |
Output is correct |
14 |
Correct |
639 ms |
23884 KB |
Output is correct |
15 |
Correct |
535 ms |
23756 KB |
Output is correct |
16 |
Correct |
640 ms |
23684 KB |
Output is correct |
17 |
Correct |
7 ms |
17876 KB |
Output is correct |
18 |
Correct |
7 ms |
17944 KB |
Output is correct |
19 |
Correct |
8 ms |
17840 KB |
Output is correct |
20 |
Correct |
9 ms |
17876 KB |
Output is correct |
21 |
Correct |
10 ms |
17976 KB |
Output is correct |
22 |
Correct |
14 ms |
17968 KB |
Output is correct |
23 |
Correct |
12 ms |
18000 KB |
Output is correct |
24 |
Correct |
12 ms |
18004 KB |
Output is correct |
25 |
Correct |
125 ms |
19104 KB |
Output is correct |
26 |
Correct |
233 ms |
20280 KB |
Output is correct |
27 |
Correct |
400 ms |
22120 KB |
Output is correct |
28 |
Correct |
420 ms |
21996 KB |
Output is correct |
29 |
Correct |
578 ms |
23828 KB |
Output is correct |
30 |
Correct |
572 ms |
23788 KB |
Output is correct |