#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=1.5e9;
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);
}
};
bool foo(q a, q b) {
return a.t < b.t;
}
void old(int n, int u, int d, int s, vector<q>&a) {
sgt st1(5e5+5), st2(5e5+5);
st1.set(s,s*d);
st2.set(s,-s*u);
sort(all(a),foo);
for(auto&x:a) {
int pos=x.p, val=x.x;
int left = st1.query(0,pos);
int right = st2.query(pos,5e5+5);
left -= pos*d;
right += pos*u;
int z=max(left,right)+val;
st1.set(pos,z+pos*d);
st2.set(pos,z-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';
exit(0);
}
void solve() {
int n,u,d,s; cin>>n>>u>>d>>s;
vector<q> a(n);
vector<vector<pi>> z(5e5+5);
int jopa=1;
forn(i,n) {
cin>>a[i].t>>a[i].p>>a[i].x;
z[a[i].t].pb({a[i].p,a[i].x});
jopa&=z[a[i].t].size()==1;
}
if (jopa) old(n,u,d,s,a);
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: 'int' and 'std::vector<std::pair<int, 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()) {
| ^~~~
salesman.cpp:104:23: warning: unused variable 'val' [-Wunused-variable]
104 | int pos=z[i][j].f, val=z[i][j].s;
| ^~~
salesman.cpp:5:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
5 | #define forn(i,n) for(int i=0;i<n;++i)
......
135 | forn(j,z[i].size()) {
| ~~~~~~~~~~~~~
salesman.cpp:135:3: note: in expansion of macro 'forn'
135 | forn(j,z[i].size()) {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
20180 KB |
Output is correct |
| 2 |
Correct |
10 ms |
20208 KB |
Output is correct |
| 3 |
Correct |
10 ms |
20312 KB |
Output is correct |
| 4 |
Correct |
11 ms |
20308 KB |
Output is correct |
| 5 |
Correct |
13 ms |
20504 KB |
Output is correct |
| 6 |
Correct |
32 ms |
21196 KB |
Output is correct |
| 7 |
Correct |
74 ms |
22428 KB |
Output is correct |
| 8 |
Correct |
150 ms |
24528 KB |
Output is correct |
| 9 |
Correct |
220 ms |
26728 KB |
Output is correct |
| 10 |
Correct |
301 ms |
33228 KB |
Output is correct |
| 11 |
Correct |
382 ms |
33188 KB |
Output is correct |
| 12 |
Correct |
533 ms |
37884 KB |
Output is correct |
| 13 |
Correct |
573 ms |
38004 KB |
Output is correct |
| 14 |
Correct |
656 ms |
42308 KB |
Output is correct |
| 15 |
Correct |
500 ms |
42316 KB |
Output is correct |
| 16 |
Correct |
603 ms |
42372 KB |
Output is correct |
| 17 |
Correct |
13 ms |
20180 KB |
Output is correct |
| 18 |
Correct |
13 ms |
20180 KB |
Output is correct |
| 19 |
Correct |
13 ms |
20252 KB |
Output is correct |
| 20 |
Correct |
14 ms |
20308 KB |
Output is correct |
| 21 |
Correct |
14 ms |
20308 KB |
Output is correct |
| 22 |
Correct |
16 ms |
20392 KB |
Output is correct |
| 23 |
Correct |
17 ms |
20436 KB |
Output is correct |
| 24 |
Correct |
17 ms |
20388 KB |
Output is correct |
| 25 |
Correct |
101 ms |
22532 KB |
Output is correct |
| 26 |
Correct |
218 ms |
25188 KB |
Output is correct |
| 27 |
Correct |
308 ms |
29072 KB |
Output is correct |
| 28 |
Correct |
357 ms |
28992 KB |
Output is correct |
| 29 |
Correct |
445 ms |
31016 KB |
Output is correct |
| 30 |
Correct |
522 ms |
32800 KB |
Output is correct |
