#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple<ll,ll,ll> tu;
struct seg {
ll up,down;
} s[1<<21];
const int mx=500005;
const ll mn=-1e18;
ll n,u,d,st,best[500010],temp1[500010],temp2[500010];
vector<tu> v; //day, location, profit
void update(int l, int r, int idx, int x, ll val_up, ll val_down) {
if (l>x || r<x) return;
if (l==r) s[idx]={val_up,val_down};
else {
int mid=(l+r)/2;
update(l,mid,2*idx,x,val_up,val_down);
update(mid+1,r,2*idx+1,x,val_up,val_down);
s[idx].up=max(s[2*idx].up,s[2*idx+1].up);
s[idx].down=max(s[2*idx].down,s[2*idx+1].down);
}
}
seg query(int l, int r, int idx, int x, int y) {
if (x>r || y<l) return {mn,mn};
if (x<=l && r<=y) return s[idx];
int mid=(l+r)/2;
seg L=query(l,mid,2*idx,x,y), R=query(mid+1,r,2*idx+1,x,y);
return {max(L.up,R.up),max(L.down,R.down)};
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
for (int i=0; i<1<<21; ++i) s[i]={mn,mn};
cin>>n>>u>>d>>st;
for (int i=0; i<n; ++i) {
ll a,b,c; cin>>a>>b>>c;
v.push_back(tu(a,b,c));
}
v.push_back(tu(mx+2,st,0));
sort(v.begin(),v.end());
update(1,mx,1,st,(mx-st)*u,(st-1)*d);
for (int i=0; i<=n; ) {
int m=1;
while (get<0>(v[i])==get<0>(v[i+m])) ++m;
ll mmax_up=mn, mmax_down=mn;
for (int j=i; j<i+m; ++j) {
ll loc=get<1>(v[j]), profit=get<2>(v[j]);
best[j]=max(query(1,mx,1,1,loc).down-(loc-1)*d, query(1,mx,1,loc+1,mx).up-(mx-loc)*u)+profit;
temp1[j]=mmax_down-d*(loc-1)+profit;
mmax_down=max(mmax_down, max(temp1[j],best[j])+d*(loc-1));
}
for (int j=i+m-1; j>=i; --j) {
ll loc=get<1>(v[j]), profit=get<2>(v[j]);
temp2[j]=mmax_up-u*(mx-loc)+profit;
mmax_up=max(mmax_up, max(best[j],temp2[j])+u*(mx-loc));
}
for (int j=i; j<i+m; ++j) {
best[j]=max({best[j],temp1[j],temp2[j]});
ll loc=get<1>(v[j]);
update(1,mx,1,loc,(mx-loc)*u+best[j],(loc-1)*d+best[j]);
}
i+=m;
}
cout<<best[n];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
33108 KB |
Output is correct |
2 |
Correct |
15 ms |
33148 KB |
Output is correct |
3 |
Correct |
14 ms |
33108 KB |
Output is correct |
4 |
Correct |
18 ms |
33248 KB |
Output is correct |
5 |
Correct |
18 ms |
33556 KB |
Output is correct |
6 |
Correct |
37 ms |
34580 KB |
Output is correct |
7 |
Correct |
68 ms |
36512 KB |
Output is correct |
8 |
Correct |
122 ms |
39764 KB |
Output is correct |
9 |
Correct |
179 ms |
42676 KB |
Output is correct |
10 |
Correct |
316 ms |
52200 KB |
Output is correct |
11 |
Correct |
338 ms |
52640 KB |
Output is correct |
12 |
Correct |
438 ms |
58076 KB |
Output is correct |
13 |
Correct |
437 ms |
58516 KB |
Output is correct |
14 |
Correct |
565 ms |
65536 KB |
Output is correct |
15 |
Correct |
528 ms |
64764 KB |
Output is correct |
16 |
Correct |
562 ms |
64712 KB |
Output is correct |
17 |
Correct |
14 ms |
33108 KB |
Output is correct |
18 |
Correct |
14 ms |
33108 KB |
Output is correct |
19 |
Correct |
17 ms |
33236 KB |
Output is correct |
20 |
Correct |
17 ms |
33348 KB |
Output is correct |
21 |
Correct |
16 ms |
33356 KB |
Output is correct |
22 |
Correct |
19 ms |
33676 KB |
Output is correct |
23 |
Correct |
18 ms |
33548 KB |
Output is correct |
24 |
Correct |
20 ms |
33516 KB |
Output is correct |
25 |
Correct |
111 ms |
39356 KB |
Output is correct |
26 |
Correct |
211 ms |
45484 KB |
Output is correct |
27 |
Correct |
341 ms |
54128 KB |
Output is correct |
28 |
Correct |
382 ms |
54984 KB |
Output is correct |
29 |
Correct |
563 ms |
63224 KB |
Output is correct |
30 |
Correct |
497 ms |
64076 KB |
Output is correct |