#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, u, d, s;
int dp[500005];
pii A[500005];
/*
struct node{
int s, e, val;
node *l, *r;
node(int _s, int _e){
s = _s, e = _e, val = -1e18;
if(s != e)l = new node(s, (s + e) >> 1), r = new node(((s + e) >> 1)+1, e);
}
void upd(int p, int v){
if(s == e)val = max(val, v);
else{
if(p <= (s + e) >> 1)l->upd(p, v);
else r->upd(p, v);
val = max(l->val, r->val);
}
}
int qry(int a, int b){
if(s == a && b == e)return val;
else if(b <= (s + e) >> 1)return l->qry(a, b);
else if(a > (s + e) >> 1)return r->qry(a, b);
else return max(l->qry(a, (s + e) >> 1), r->qry(((s + e) >> 1) +1, b));
}
}*dwn, *up;
*/
int dwn[2000005], up[2000005], tmp[2000005], tmp2[2000005], dp2[500005];
void build(int t[], int v, int tl, int tr) {
if (tl == tr) {
t[v] = -1e18;
} else {
int tm = (tl + tr) / 2;
build(t, v*2, tl, tm);
build(t, v*2+1, tm+1, tr);
t[v] = max(t[v*2], t[v*2+1]);
}
}
void update(int t[], int v, int tl, int tr, int pos, int new_val) {
if (tl == tr) {
t[v] = max(t[v], new_val);
} else {
int tm = (tl + tr) / 2;
if (pos <= tm)
update(t, v*2, tl, tm, pos, new_val);
else
update(t, v*2+1, tm+1, tr, pos, new_val);
t[v] = max(t[v*2], t[v*2+1]);
}
}
void upd(int t[], int v, int tl, int tr, int pos, int new_val) {
if (tl == tr) {
t[v] = new_val;
} else {
int tm = (tl + tr) / 2;
if (pos <= tm)
upd(t, v*2, tl, tm, pos, new_val);
else
upd(t, v*2+1, tm+1, tr, pos, new_val);
t[v] = max(t[v*2], t[v*2+1]);
}
}
int sum(int t[], int v, int tl, int tr, int l, int r) {
if (l > r)
return -1e18;
if (l == tl && r == tr) {
return t[v];
}
int tm = (tl + tr) / 2;
return max(sum(t, v*2, tl, tm, l, min(r, tm)),
sum(t, v*2+1, tm+1, tr, max(l, tm+1), r));
}
void solve(){
cin >> n >> u >> d >> s;
int mx = s;
for(int i=1;i<=n;i++){
cin >> A[i].fi >> A[i].se.fi >> A[i].se.se;
mx = max(mx, A[i].se.fi);
}
sort(A+1, A+n+1);
A[0].se.fi = s;
A[n+1].se.fi = s;
build(dwn, 1, 1, mx );
build(up, 1, 1, mx );
update(dwn, 1, 1, mx, s, -d * s);
update(up, 1, 1, mx, s, u * s);
build(tmp, 1, 1, mx);
build(tmp2, 1, 1, mx);
for(int i=1;i<=n+1;i++){
int j = i + 1;
while(j <= n && A[j].fi == A[i].fi)j++;
j--;
for(int x=j;x>=i;x--){
int top = max(sum(dwn, 1, 1, mx, A[x].se.fi, mx), sum(tmp, 1, 1, mx, A[x].se.fi, mx)) + d * A[x].se.fi + A[x].se.se;
int bot = max(sum(up, 1, 1, mx, 1, A[x].se.fi), sum(tmp2, 1, 1, mx, 1, A[x].se.fi)) - u * A[x].se.fi + A[x].se.se;
dp2[x] = max(top, bot);
update(tmp, 1, 1, mx, A[x].se.fi, dp2[x] - d * A[x].se.fi);
update(tmp2, 1, 1, mx, A[x].se.fi, dp2[x] + u * A[x].se.fi);
}
for(int x=i;x<=j;x++){
int top = max(sum(dwn, 1, 1, mx, A[x].se.fi, mx), (int)-1e18) + d * A[x].se.fi + A[x].se.se;
int bot = max(sum(up, 1, 1, mx, 1, A[x].se.fi), (int)-1e18) - u * A[x].se.fi + A[x].se.se;
dp[x] = max(top, bot);
update(dwn, 1, 1, mx, A[x].se.fi, dp[x] - d * A[x].se.fi);
update(up, 1, 1, mx, A[x].se.fi, dp[x] + u * A[x].se.fi);
}
for(int x=i;x<=j;x++)dp[x] = max(dp[x], dp2[x]);
for(int x=i;x<=j;x++){
update(dwn, 1, 1, mx, A[x].se.fi, dp[x] - d * A[x].se.fi);
update(up, 1, 1, mx, A[x].se.fi, dp[x] + u * A[x].se.fi);
upd(tmp, 1, 1, mx, A[x].se.fi, -1e18);
upd(tmp2, 1, 1, mx, A[x].se.fi, -1e18);
}
i = j;
//int top = dwn->qry(A[i].se.fi, mx) + d * A[i].se.fi + A[i].se.se;
//int bot = up->qry(1, A[i].se.fi) - u * A[i].se.fi + A[i].se.se;
/*
for(int j=i-1;j>=0;j--){
int cst;
if(A[j].se.fi > A[i].se.fi)cst = d * (A[j].se.fi - A[i].se.fi);
else cst = u * (A[i].se.fi - A[j].se.fi);
dp[i] = max(dp[i], dp[j] - cst + A[i].se.se);
}
*/
//dwn->upd(A[i].se.fi, dp[i] - d * A[i].se.fi);
//up->upd(A[i].se.fi, dp[i] + u * A[i].se.fi);
}
cout << dp[n+1];
}
main(){
ios::sync_with_stdio(0);cin.tie(0);
int tc = 1;
//cin >> tc;
for(int tc1=1;tc1<=tc;tc1++){
// cout << "Case #" << tc1 << ": ";
solve();
}
}
Compilation message
salesman.cpp:147:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
147 | main(){
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
392 KB |
Output is correct |
| 3 |
Correct |
2 ms |
852 KB |
Output is correct |
| 4 |
Correct |
3 ms |
596 KB |
Output is correct |
| 5 |
Correct |
10 ms |
1008 KB |
Output is correct |
| 6 |
Correct |
85 ms |
33868 KB |
Output is correct |
| 7 |
Correct |
187 ms |
35124 KB |
Output is correct |
| 8 |
Correct |
344 ms |
37112 KB |
Output is correct |
| 9 |
Correct |
508 ms |
39044 KB |
Output is correct |
| 10 |
Correct |
850 ms |
44888 KB |
Output is correct |
| 11 |
Correct |
1014 ms |
44924 KB |
Output is correct |
| 12 |
Correct |
1336 ms |
48916 KB |
Output is correct |
| 13 |
Correct |
1309 ms |
48904 KB |
Output is correct |
| 14 |
Correct |
1606 ms |
52688 KB |
Output is correct |
| 15 |
Correct |
1328 ms |
52740 KB |
Output is correct |
| 16 |
Correct |
1639 ms |
52684 KB |
Output is correct |
| 17 |
Correct |
0 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
340 KB |
Output is correct |
| 19 |
Correct |
2 ms |
468 KB |
Output is correct |
| 20 |
Correct |
4 ms |
724 KB |
Output is correct |
| 21 |
Correct |
4 ms |
724 KB |
Output is correct |
| 22 |
Correct |
9 ms |
980 KB |
Output is correct |
| 23 |
Correct |
9 ms |
1040 KB |
Output is correct |
| 24 |
Correct |
9 ms |
980 KB |
Output is correct |
| 25 |
Correct |
352 ms |
37036 KB |
Output is correct |
| 26 |
Correct |
610 ms |
40936 KB |
Output is correct |
| 27 |
Correct |
1016 ms |
46820 KB |
Output is correct |
| 28 |
Correct |
1158 ms |
46852 KB |
Output is correct |
| 29 |
Correct |
1672 ms |
52700 KB |
Output is correct |
| 30 |
Correct |
1584 ms |
52672 KB |
Output is correct |
