#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
const int inf=2e9;
struct SegmentTree{
int n;
vector<int> t;
void init(int _n){
n=_n;
t.assign(4*n+1, -inf);
}
void update(int k, int l, int r, int pos, int val){
if (l==r){
t[k]=val;
return;
}
int mid=(l+r)>>1;
if (pos<=mid) update(k<<1, l, mid, pos, val);
else update(k<<1|1, mid+1, r, pos, val);
t[k]=max(t[k<<1], t[k<<1|1]);
}
int get(int k, int l, int r, int L, int R){
if (r<L || R<l) return -inf;
if (L<=l && r<=R) return t[k];
int mid=(l+r)>>1;
return max(get(k<<1, l, mid, L, R), get(k<<1|1, mid+1, r, L, R));
}
} st1, st2;
int n, s, f[N], f1[N], f2[N], val[0], tt[0];
int u, d;
set<int> st;
vector<int> v[N];
void calc(int t){
vector<int> &vv=v[t];
sort(vv.begin(), vv.end());
for (auto &i:vv){
f1[i]=f2[i]=max(st1.get(1, 1, st1.n, 1, i)-d*i, st2.get(1, 1, st2.n, i, st2.n)+u*i);
}
f2[vv[0]]+=val[vv[0]];
f1[vv.back()]+=val[vv.back()];
for (int i=1; i<(int)vv.size(); ++i) f2[vv[i]]=max(f2[vv[i]], f2[vv[i-1]]-d*(vv[i]-vv[i-1]))+val[vv[i]];
for (int i=(int)vv.size()-2; i>=0; --i) f1[vv[i]]=max(f1[vv[i]], f1[vv[i+1]]-u*(vv[i+1]-vv[i]))+val[vv[i]];
for (int i:vv){
f[i]=max(f1[i], f2[i]);
st1.update(1, 1, st1.n, i, f[i]+d*i);
st2.update(1, 1, st2.n, i, f[i]-u*i);
}
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> u >> d >> s;
for (int i=1; i<=n; ++i){
int t, l, m; cin >> t >> l >> m;
v[t].push_back(l);
tt[l]=t;
val[l]=m;
st.insert(t);
}
st1.init(N); st2.init(N);
st.insert(0);
for (int i=0; i<N; ++i) f[i]=-inf;
f[s]=0;
st1.update(1, 1, st1.n, s, f[s]+d*s);
st2.update(1, 1, st2.n, s, f[s]-u*s);
v[0].push_back(s);
v[500001].push_back(s);
st.insert(500001);
for (auto it=next(st.begin()); it!=st.end(); ++it){
calc(*it);
}
cout << f[s] << '\n';
return 0;
}
Compilation message
salesman.cpp: In function 'void calc(int)':
salesman.cpp:44:24: warning: array subscript <unknown> is outside array bounds of 'int [0]' [-Warray-bounds]
44 | f2[vv[0]]+=val[vv[0]];
| ~~~~~~~~~^
salesman.cpp:33:31: note: while referencing 'val'
33 | int n, s, f[N], f1[N], f2[N], val[0], tt[0];
| ^~~
salesman.cpp:45:32: warning: array subscript <unknown> is outside array bounds of 'int [0]' [-Warray-bounds]
45 | f1[vv.back()]+=val[vv.back()];
| ~~~~~~~~~~~~~^
salesman.cpp:33:31: note: while referencing 'val'
33 | int n, s, f[N], f1[N], f2[N], val[0], tt[0];
| ^~~
salesman.cpp:47:109: warning: array subscript <unknown> is outside array bounds of 'int [0]' [-Warray-bounds]
47 | for (int i=(int)vv.size()-2; i>=0; --i) f1[vv[i]]=max(f1[vv[i]], f1[vv[i+1]]-u*(vv[i+1]-vv[i]))+val[vv[i]];
| ~~~~~~~~~^
salesman.cpp:33:31: note: while referencing 'val'
33 | int n, s, f[N], f1[N], f2[N], val[0], tt[0];
| ^~~
salesman.cpp:46:106: warning: array subscript <unknown> is outside array bounds of 'int [0]' [-Warray-bounds]
46 | for (int i=1; i<(int)vv.size(); ++i) f2[vv[i]]=max(f2[vv[i]], f2[vv[i-1]]-d*(vv[i]-vv[i-1]))+val[vv[i]];
| ~~~~~~~~~^
salesman.cpp:33:31: note: while referencing 'val'
33 | int n, s, f[N], f1[N], f2[N], val[0], tt[0];
| ^~~
salesman.cpp: In function 'int32_t main()':
salesman.cpp:62:11: warning: array subscript <unknown> is outside array bounds of 'int [0]' [-Warray-bounds]
62 | tt[l]=t;
| ~~~~^
salesman.cpp:33:39: note: while referencing 'tt'
33 | int n, s, f[N], f1[N], f2[N], val[0], tt[0];
| ^~
salesman.cpp:63:12: warning: array subscript <unknown> is outside array bounds of 'int [0]' [-Warray-bounds]
63 | val[l]=m;
| ~~~~~^
salesman.cpp:33:31: note: while referencing 'val'
33 | int n, s, f[N], f1[N], f2[N], val[0], tt[0];
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
33624 KB |
Output is correct |
| 2 |
Correct |
7 ms |
33632 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
33628 KB |
Output isn't correct |
| 4 |
Incorrect |
7 ms |
33884 KB |
Output isn't correct |
| 5 |
Incorrect |
12 ms |
33884 KB |
Output isn't correct |
| 6 |
Incorrect |
24 ms |
35308 KB |
Output isn't correct |
| 7 |
Incorrect |
63 ms |
37616 KB |
Output isn't correct |
| 8 |
Incorrect |
124 ms |
41556 KB |
Output isn't correct |
| 9 |
Incorrect |
172 ms |
45404 KB |
Output isn't correct |
| 10 |
Incorrect |
339 ms |
57168 KB |
Output isn't correct |
| 11 |
Incorrect |
397 ms |
57144 KB |
Output isn't correct |
| 12 |
Incorrect |
514 ms |
64804 KB |
Output isn't correct |
| 13 |
Incorrect |
541 ms |
65032 KB |
Output isn't correct |
| 14 |
Runtime error |
322 ms |
65536 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
301 ms |
65536 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
322 ms |
65536 KB |
Execution killed with signal 9 |
| 17 |
Incorrect |
7 ms |
33624 KB |
Output isn't correct |
| 18 |
Incorrect |
7 ms |
33628 KB |
Output isn't correct |
| 19 |
Incorrect |
8 ms |
33628 KB |
Output isn't correct |
| 20 |
Incorrect |
9 ms |
33528 KB |
Output isn't correct |
| 21 |
Incorrect |
8 ms |
33660 KB |
Output isn't correct |
| 22 |
Incorrect |
9 ms |
33824 KB |
Output isn't correct |
| 23 |
Incorrect |
9 ms |
33628 KB |
Output isn't correct |
| 24 |
Incorrect |
10 ms |
33628 KB |
Output isn't correct |
| 25 |
Incorrect |
66 ms |
34212 KB |
Output isn't correct |
| 26 |
Incorrect |
122 ms |
34804 KB |
Output isn't correct |
| 27 |
Incorrect |
186 ms |
35396 KB |
Output isn't correct |
| 28 |
Incorrect |
264 ms |
36692 KB |
Output isn't correct |
| 29 |
Incorrect |
245 ms |
36180 KB |
Output isn't correct |
| 30 |
Incorrect |
246 ms |
36324 KB |
Output isn't correct |
