#include <bits/stdc++.h>
using namespace std;
#define int long long
#define forn(i,n) for(int i=0;i<n;++i)
#define pi pair<int,int>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vii(a,n) vector<int>a(n);forn(i,n)cin>>a[i];
const int inf=1e18;
struct q {
int t,p,x;
};
struct sgt {
vector<int> t; int sz=1;
sgt(int n) {
while (sz<n) sz<<=1;
t.assign(2*sz-1,-inf);
}
void upd(int v, int l, int r, int i) {
if (r-l==1) return;
int m=(l+r)>>1;
if (i<m) upd(2*v+1,l,m,i);
else upd(2*v+2,m,r,i);
t[v]=max(t[2*v+1],t[2*v+2]);
}
void set(int i, int x) {
t[sz-1+i]=x;
upd(0,0,sz,i);
}
int query(int v, int l, int r, int lx, int rx) {
if (rx<=l || r<=lx) return -inf;
if (lx<=l && r<=rx) return t[v];
int m=(l+r)>>1;
int lq=query(2*v+1,l,m,lx,rx);
int rq=query(2*v+2,m,r,lx,rx);
return max(lq,rq);
}
int query(int l, int r) {
return query(0,0,sz,l,r);
}
};
void solve() {
int n,u,d,s; cin>>n>>u>>d>>s;
vector<q> a(n);
vector<vector<pi>> z(5e5+5);
forn(i,n) {
cin>>a[i].t>>a[i].p>>a[i].x;
z[a[i].t].pb({a[i].p,a[i].x});
}
forn(i,5e5+5) sort(all(z[i]));
sgt st1(5e5+5), st2(5e5+5);
st1.set(s,s*d);
st2.set(s,-s*u);
forn(i,5e5+5){
if (!z[i].size()) continue;
sort(all(z[i]));
vector<int> q(z[i].size(),-inf);
vector<int> p(z[i].size(),-inf);
forn(j,z[i].size()) {
int pos=z[i][j].f, val=z[i][j].s;
int left = st1.query(0,pos);
int right = st2.query(pos,5e5+5);
left -= pos*d;
right += pos*u;
int zzz=max(left,right);
p[j]=zzz;
}
int m=z[i].size();
vector<int> pr(m+1,0);
vector<int> dist(m,0);
forn(j,m) pr[j+1]=pr[j]+z[i][j].s;
forn(j,m) dist[j]=(z[i][j].f-z[i][0].f)*u;
vector<int> dp(m+1,0);
dp[m]=pr[m]+p[m-1]-dist[m-1];
for (int j=m-1; j; --j) dp[j]=max(dp[j+1],pr[j]+p[j-1]-dist[j-1]);
forn(j,m) q[j]=max(q[j],dp[j+1]-pr[j]+dist[j]);
reverse(all(z[i]));
reverse(all(p));
reverse(all(q));
forn(j,m) pr[j+1]=pr[j]+z[i][j].s;
forn(j,m) dist[j]=(z[i][0].f-z[i][j].f)*d;
dp[m]=pr[m]+p[m-1]-dist[m-1];
for (int j=m-1; j; --j) dp[j]=max(dp[j+1],pr[j]+p[j-1]-dist[j-1]);
forn(j,m) q[j]=max(q[j],dp[j+1]-pr[j]+dist[j]);
reverse(all(q));
reverse(all(z[i]));
forn(j,z[i].size()) {
int pos=z[i][j].f;
int zzz=q[j];
st1.set(pos,zzz+pos*d);
st2.set(pos,zzz-pos*u);
}
}
int left = st1.query(0,s);
left -= s*d;
int right = st2.query(s,5e5+5);
right += s*u;
int ans = max(left,right);
cout<<ans<<'\n';
}
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
solve();
}
Compilation message
salesman.cpp: In function 'void solve()':
salesman.cpp:5:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
5 | #define forn(i,n) for(int i=0;i<n;++i)
......
71 | forn(j,z[i].size()) {
| ~~~~~~~~~~~~~
salesman.cpp:71:3: note: in expansion of macro 'forn'
71 | forn(j,z[i].size()) {
| ^~~~
salesman.cpp:72:23: warning: unused variable 'val' [-Wunused-variable]
72 | int pos=z[i][j].f, val=z[i][j].s;
| ^~~
salesman.cpp:5:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
5 | #define forn(i,n) for(int i=0;i<n;++i)
......
103 | forn(j,z[i].size()) {
| ~~~~~~~~~~~~~
salesman.cpp:103:3: note: in expansion of macro 'forn'
103 | forn(j,z[i].size()) {
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
28372 KB |
Output is correct |
2 |
Correct |
13 ms |
28476 KB |
Output is correct |
3 |
Correct |
13 ms |
28500 KB |
Output is correct |
4 |
Correct |
14 ms |
28624 KB |
Output is correct |
5 |
Correct |
17 ms |
28832 KB |
Output is correct |
6 |
Correct |
36 ms |
29860 KB |
Output is correct |
7 |
Correct |
73 ms |
32124 KB |
Output is correct |
8 |
Correct |
134 ms |
35656 KB |
Output is correct |
9 |
Correct |
194 ms |
39064 KB |
Output is correct |
10 |
Correct |
326 ms |
49648 KB |
Output is correct |
11 |
Correct |
412 ms |
50292 KB |
Output is correct |
12 |
Correct |
515 ms |
56512 KB |
Output is correct |
13 |
Correct |
519 ms |
56724 KB |
Output is correct |
14 |
Correct |
624 ms |
64828 KB |
Output is correct |
15 |
Correct |
515 ms |
63984 KB |
Output is correct |
16 |
Correct |
645 ms |
63940 KB |
Output is correct |
17 |
Correct |
13 ms |
28500 KB |
Output is correct |
18 |
Correct |
13 ms |
28500 KB |
Output is correct |
19 |
Correct |
13 ms |
28500 KB |
Output is correct |
20 |
Correct |
14 ms |
28628 KB |
Output is correct |
21 |
Correct |
15 ms |
28628 KB |
Output is correct |
22 |
Correct |
16 ms |
28756 KB |
Output is correct |
23 |
Correct |
16 ms |
28884 KB |
Output is correct |
24 |
Correct |
17 ms |
28804 KB |
Output is correct |
25 |
Correct |
92 ms |
34252 KB |
Output is correct |
26 |
Correct |
167 ms |
41232 KB |
Output is correct |
27 |
Correct |
283 ms |
50620 KB |
Output is correct |
28 |
Correct |
290 ms |
50636 KB |
Output is correct |
29 |
Correct |
395 ms |
55976 KB |
Output is correct |
30 |
Correct |
385 ms |
60768 KB |
Output is correct |