#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 |
15 ms |
28372 KB |
Output is correct |
| 2 |
Correct |
16 ms |
28444 KB |
Output is correct |
| 3 |
Correct |
16 ms |
28500 KB |
Output is correct |
| 4 |
Correct |
18 ms |
28528 KB |
Output is correct |
| 5 |
Correct |
20 ms |
28672 KB |
Output is correct |
| 6 |
Correct |
51 ms |
29480 KB |
Output is correct |
| 7 |
Correct |
93 ms |
31200 KB |
Output is correct |
| 8 |
Correct |
204 ms |
33964 KB |
Output is correct |
| 9 |
Correct |
276 ms |
36700 KB |
Output is correct |
| 10 |
Correct |
432 ms |
44928 KB |
Output is correct |
| 11 |
Correct |
494 ms |
44920 KB |
Output is correct |
| 12 |
Correct |
629 ms |
50400 KB |
Output is correct |
| 13 |
Correct |
677 ms |
50368 KB |
Output is correct |
| 14 |
Correct |
843 ms |
55868 KB |
Output is correct |
| 15 |
Correct |
708 ms |
55888 KB |
Output is correct |
| 16 |
Correct |
873 ms |
56004 KB |
Output is correct |
| 17 |
Correct |
16 ms |
28496 KB |
Output is correct |
| 18 |
Correct |
16 ms |
28500 KB |
Output is correct |
| 19 |
Correct |
18 ms |
28468 KB |
Output is correct |
| 20 |
Correct |
23 ms |
28616 KB |
Output is correct |
| 21 |
Correct |
19 ms |
28624 KB |
Output is correct |
| 22 |
Correct |
20 ms |
28756 KB |
Output is correct |
| 23 |
Correct |
19 ms |
28756 KB |
Output is correct |
| 24 |
Correct |
19 ms |
28756 KB |
Output is correct |
| 25 |
Correct |
144 ms |
33008 KB |
Output is correct |
| 26 |
Correct |
220 ms |
38416 KB |
Output is correct |
| 27 |
Correct |
352 ms |
46256 KB |
Output is correct |
| 28 |
Correct |
445 ms |
45340 KB |
Output is correct |
| 29 |
Correct |
525 ms |
49416 KB |
Output is correct |
| 30 |
Correct |
533 ms |
53384 KB |
Output is correct |
