#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <algorithm>
using namespace std;
typedef int INT;
const INT nmax=500005;
INT n,m,st,dr,i,j,t,wh,prof;
INT u,d,poz,s,val,mx,k,p,nr,sum,maxi;
INT opt[nmax],gg[nmax];
struct tr
{
INT t,first,second;
}v[nmax];
bool comp(tr unu,tr doi)
{
if(unu.t==doi.t&&unu.first==doi.first) return unu.second<doi.second;
if(unu.t==doi.t)return unu.first<doi.first;
return unu.t<doi.t;
}
struct aint
{
INT arb[3*nmax];
void update(INT nod,INT l,INT r)
{
arb[nod]=max(arb[nod],val);
if(l==r) return;
INT m=(l+r)/2;
if(poz<=m) update(2*nod,l,m);
else update(2*nod+1,m+1,r);
}
void query(INT nod,INT l,INT r)
{
if(st<=l&&r<=dr)
{
mx=max(arb[nod],mx);
return;
}
INT m=(l+r)/2;
if(st<=m) query(2*nod,l,m);
if(m<dr) query(2*nod+1,m+1,r);
}
}A[2];
//upstream la stanga
//downstream la dreapta
void recalc()
{
val=opt[poz]+poz*d;
A[0].update(1,1,n);
val=opt[poz]-poz*u;
A[1].update(1,1,n);
}
INT get_opt(INT poz)
{
INT ret=INT_MIN;
mx=INT_MIN;st=1;dr=poz;
A[0].query(1,1,n);
if(mx!=INT_MIN)ret=max(ret,mx-poz*d);
mx=INT_MIN;st=poz;dr=n;
A[1].query(1,1,n);
if(mx!=INT_MIN)ret=max(ret,mx+poz*u);
return ret;
}
int main()
{
//freopen("data.in","r",stdin);
ios_base::sync_with_stdio(false);
cin>>n>>u>>d>>s;
for(i=1;i<=n;i++)
{
++nr;
cin>>v[i].t>>v[i].first>>v[i].second;
}
n=5*100*1000+1;
for(i=1;i<=3*n;i++)
A[0].arb[i]=A[1].arb[i]=INT_MIN;
poz=s;val=0;
recalc();
sort(v+1,v+nr+1,comp);
for(i=1;i<=nr;i++)
{
p=i;
while(p<=nr&&v[i].t==v[p].t)
p++;
p--;
maxi=INT_MIN;sum=0;
for(j=i;j<=p;j++)
{
poz=v[j].first;
gg[poz]=get_opt(poz);
k=gg[poz]+poz*d-sum;
if(k>maxi) maxi=k;
sum+=v[j].second;
opt[poz]=maxi-poz*d+sum;
}
maxi=INT_MIN;sum=0;
for(j=p;j>=i;j--)
{
poz=v[j].first;
k=gg[poz]-poz*u-sum;
if(k>maxi) maxi=k;
sum+=v[j].second;
opt[poz]=max(opt[poz],maxi+poz*u+sum);
recalc();
}
i=p;
}
cout<<get_opt(s);
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
12024 KB |
Output is correct |
2 |
Correct |
12 ms |
12260 KB |
Output is correct |
3 |
Correct |
12 ms |
12260 KB |
Output is correct |
4 |
Correct |
17 ms |
12380 KB |
Output is correct |
5 |
Correct |
16 ms |
12420 KB |
Output is correct |
6 |
Correct |
58 ms |
16428 KB |
Output is correct |
7 |
Correct |
143 ms |
16812 KB |
Output is correct |
8 |
Correct |
249 ms |
17540 KB |
Output is correct |
9 |
Correct |
290 ms |
17972 KB |
Output is correct |
10 |
Correct |
471 ms |
19896 KB |
Output is correct |
11 |
Correct |
662 ms |
19896 KB |
Output is correct |
12 |
Correct |
660 ms |
21076 KB |
Output is correct |
13 |
Correct |
692 ms |
21100 KB |
Output is correct |
14 |
Correct |
850 ms |
22208 KB |
Output is correct |
15 |
Correct |
873 ms |
22220 KB |
Output is correct |
16 |
Correct |
910 ms |
22220 KB |
Output is correct |
17 |
Correct |
13 ms |
22220 KB |
Output is correct |
18 |
Correct |
12 ms |
22220 KB |
Output is correct |
19 |
Correct |
13 ms |
22220 KB |
Output is correct |
20 |
Correct |
14 ms |
22220 KB |
Output is correct |
21 |
Correct |
14 ms |
22220 KB |
Output is correct |
22 |
Correct |
19 ms |
22220 KB |
Output is correct |
23 |
Correct |
16 ms |
22220 KB |
Output is correct |
24 |
Correct |
16 ms |
22220 KB |
Output is correct |
25 |
Correct |
203 ms |
22220 KB |
Output is correct |
26 |
Correct |
359 ms |
22220 KB |
Output is correct |
27 |
Correct |
665 ms |
22220 KB |
Output is correct |
28 |
Correct |
691 ms |
22220 KB |
Output is correct |
29 |
Correct |
950 ms |
22268 KB |
Output is correct |
30 |
Correct |
970 ms |
22288 KB |
Output is correct |