#include<bits/stdc++.h>
#include<fstream>
using namespace std;
//ifstream fin("INTERNET.INP");
//ofstream fout("INTERNET.OUT");
#define ll long long
#define vt vector
#define pb push_back
#define fi first
#define se second
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define int long long
typedef unsigned long long ull;
const int mxn = 5e5 + 3;
struct ST{
int mx[mxn * 4 + 1];
void init(){
for(int i = 1; i <= 4 * mxn; i++)mx[i] = -1e9;
}
void upd(int nd, int l, int r, int id, int v){
if(id < l || id > r)return;
if(l == r){
mx[nd] = v; return;
}
int mid = (l + r) >> 1;
upd(nd * 2, l, mid, id, v); upd(nd * 2 + 1, mid + 1, r, id, v);
mx[nd] = max(mx[nd * 2], mx[nd * 2 + 1]);
}
int get(int nd, int l, int r, int ql, int qr){
if(ql > r || qr < l)return(-1e9);
if(ql <= l && qr >= r)return(mx[nd]);
int mid = (l + r) >> 1;
return(max(get(nd * 2, l, mid, ql, qr), get(nd * 2 + 1, mid + 1, r, ql, qr)));
}
};
struct th{
int t, l, m;
bool operator <(const th &b){
if(t != b.t)return(t < b.t);
return(l < b.l);
}
};
ST down, up;
//down -> go down up -> go up
int n, d, u, s;
int dp[mxn + 1];
ll test[mxn + 1], test2[mxn + 1];
vt<th>v;
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
down.init(); up.init();
cin >> n >> d >> u >> s;
forr(i, 0, n){
int t, l, m; cin >> t >> l >> m;
v.pb({t, l, m});
}
v.pb({mxn + 69, s, 0});
sort(v.begin(), v.end());
down.upd(1, 1, mxn, s, -d * s); up.upd(1, 1, mxn, s, u * s);
int r = 0;
for(int i = 0; i < v.size();){
while(r < v.size() && v[r].t == v[i].t)r++;
int mxup = -1e9;
for(int j = i; j < r; j++){
dp[j] = max(down.get(1, 1, mxn, v[j].l, mxn) + d * v[j].l, up.get(1, 1, mxn, 1, v[j].l) - u * v[j].l) + v[j].m;
test[j] = mxup - u * v[j].l + v[j].m;
mxup = max(mxup, max(dp[j], test[j]) + u * v[j].l);
}
int mxdown = -1e9;
for(int j = r - 1; j >= i; j--){
test2[j] = mxdown + d * v[j].l + v[j].m;
mxdown = max(mxdown, max(dp[j], test2[j]) - d * v[j].l);
}
for(int j = i; j < r; j++){
dp[j] = max({dp[j], test[j], test2[j]});
down.upd(1, 1, mxn, v[j].l, dp[j] - d * v[j].l); up.upd(1, 1, mxn, v[j].l, dp[j] + u * v[j].l);
}
i = r;
}
cout << dp[v.size() - 1];
return 0;
}
Compilation message
salesman.cpp: In function 'int main()':
salesman.cpp:69:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<th>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for(int i = 0; i < v.size();){
| ~~^~~~~~~~~~
salesman.cpp:70:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<th>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | while(r < v.size() && v[r].t == v[i].t)r++;
| ~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
31572 KB |
Output is correct |
2 |
Correct |
13 ms |
31572 KB |
Output is correct |
3 |
Correct |
14 ms |
31572 KB |
Output is correct |
4 |
Correct |
17 ms |
31780 KB |
Output is correct |
5 |
Correct |
18 ms |
32016 KB |
Output is correct |
6 |
Correct |
38 ms |
32708 KB |
Output is correct |
7 |
Correct |
77 ms |
34084 KB |
Output is correct |
8 |
Correct |
129 ms |
36400 KB |
Output is correct |
9 |
Correct |
188 ms |
38784 KB |
Output is correct |
10 |
Correct |
344 ms |
45804 KB |
Output is correct |
11 |
Correct |
377 ms |
45896 KB |
Output is correct |
12 |
Correct |
544 ms |
50532 KB |
Output is correct |
13 |
Correct |
502 ms |
50520 KB |
Output is correct |
14 |
Correct |
709 ms |
55208 KB |
Output is correct |
15 |
Correct |
535 ms |
55240 KB |
Output is correct |
16 |
Correct |
639 ms |
55216 KB |
Output is correct |
17 |
Correct |
19 ms |
31572 KB |
Output is correct |
18 |
Correct |
14 ms |
31632 KB |
Output is correct |
19 |
Correct |
14 ms |
31680 KB |
Output is correct |
20 |
Correct |
19 ms |
31828 KB |
Output is correct |
21 |
Correct |
19 ms |
31848 KB |
Output is correct |
22 |
Correct |
17 ms |
31996 KB |
Output is correct |
23 |
Correct |
17 ms |
32020 KB |
Output is correct |
24 |
Correct |
17 ms |
32020 KB |
Output is correct |
25 |
Correct |
148 ms |
36404 KB |
Output is correct |
26 |
Correct |
219 ms |
41132 KB |
Output is correct |
27 |
Correct |
351 ms |
48200 KB |
Output is correct |
28 |
Correct |
393 ms |
48264 KB |
Output is correct |
29 |
Correct |
519 ms |
55212 KB |
Output is correct |
30 |
Correct |
525 ms |
55296 KB |
Output is correct |