#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAX_N = 5e5 + 5, MAX_POS = 5e5 + 5, INF = 2e18 + 5;
int n, l, r, s;
int day[MAX_N], pos[MAX_N], val[MAX_N];
map<int, vector<int>> days;
int st[2][4 * MAX_N];
void build(int ind) {
for (int i = 1; i <= 4 * MAX_POS; i++) st[ind][i] = -INF;
}
void update(int ind, int i, int x, int u = 1, int lo = 1, int hi = MAX_POS) {
if (i < lo || hi < i) return;
if (lo == hi) { st[ind][u] = x; return; }
int mid = (lo + hi) / 2;
update(ind, i, x, 2 * u, lo, mid), update(ind, i, x, 2 * u + 1, mid + 1, hi);
st[ind][u] = max(st[ind][2 * u], st[ind][2 * u + 1]);
}
int query(int ind, int l, int r, int u = 1, int lo = 1, int hi = MAX_POS) {
if (r < lo || hi < l) return -INF;
if (l <= lo && hi <= r) return st[ind][u];
int mid = (lo + hi) / 2;
return max(query(ind, l, r, 2 * u, lo, mid), query(ind, l, r, 2 * u + 1, mid + 1, hi));
}
int dp[MAX_N];
void init() {
build(0), build(1);
day[0] = 0, pos[0] = s, val[0] = 0, dp[0] = 0;
update(0, pos[0], pos[0] * r), update(1, pos[0], -pos[0] * l);
day[n + 1] = INF, pos[n + 1] = s, val[n + 1] = 0, days[INF].push_back(n + 1);
}
signed main() {
// freopen("salesman.in", "r", stdin), freopen("salesman.out", "w", stdout);
cin >> n >> l >> r >> s;
init();
for (int i = 1; i <= n; i++)
cin >> day[i] >> pos[i] >> val[i], days[day[i]].push_back(i);
for (pair<int, vector<int>> x : days) {
auto comp = [] (int i, int j)->bool { return pos[i] < pos[j]; };
sort(x.second.begin(), x.second.end(), comp);
// cout << "NEW --------------" << x.first << endl;
for (int i = 0; i <= (int) x.second.size() - 1; i++) {
int ind = x.second[i];
int l_trans = query(0, 1, pos[ind]) - pos[ind] * r;
int r_trans = query(1, pos[ind] + 1, MAX_POS) + pos[ind] * l;
int step_trans = (i == 0) ? -INF : dp[x.second[i - 1]] + r * (pos[ind] - pos[x.second[i - 1]]);
// cout << ind << ": " << l_trans << " " << r_trans << " " << step_trans << endl;
dp[ind] = max({l_trans, r_trans, step_trans}) + val[ind];
}
for (int ind : x.second)
update(0, pos[ind], dp[ind] + pos[ind] * r), update(1, pos[ind], dp[ind] - pos[ind] * l);
}
cout << dp[n + 1] << '\n';
}
Compilation message
salesman.cpp: In function 'void build(long long int)':
salesman.cpp:12:55: warning: iteration 2000019 invokes undefined behavior [-Waggressive-loop-optimizations]
12 | for (int i = 1; i <= 4 * MAX_POS; i++) st[ind][i] = -INF;
| ~~~~~~~~~~~^~~~~~
salesman.cpp:12:23: note: within this loop
12 | for (int i = 1; i <= 4 * MAX_POS; i++) st[ind][i] = -INF;
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
39260 KB |
Output is correct |
| 2 |
Correct |
5 ms |
39260 KB |
Output is correct |
| 3 |
Correct |
6 ms |
39424 KB |
Output is correct |
| 4 |
Correct |
7 ms |
39516 KB |
Output is correct |
| 5 |
Correct |
12 ms |
42076 KB |
Output is correct |
| 6 |
Correct |
44 ms |
44124 KB |
Output is correct |
| 7 |
Correct |
112 ms |
52056 KB |
Output is correct |
| 8 |
Correct |
252 ms |
58708 KB |
Output is correct |
| 9 |
Correct |
312 ms |
64340 KB |
Output is correct |
| 10 |
Runtime error |
214 ms |
65536 KB |
Execution killed with signal 9 |
| 11 |
Runtime error |
205 ms |
65536 KB |
Execution killed with signal 9 |
| 12 |
Runtime error |
187 ms |
65536 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
213 ms |
65536 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
251 ms |
65536 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
198 ms |
65536 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
209 ms |
65536 KB |
Execution killed with signal 9 |
| 17 |
Incorrect |
7 ms |
39260 KB |
Output isn't correct |
| 18 |
Incorrect |
6 ms |
39260 KB |
Output isn't correct |
| 19 |
Incorrect |
5 ms |
39260 KB |
Output isn't correct |
| 20 |
Incorrect |
7 ms |
39516 KB |
Output isn't correct |
| 21 |
Incorrect |
8 ms |
39516 KB |
Output isn't correct |
| 22 |
Incorrect |
11 ms |
41564 KB |
Output isn't correct |
| 23 |
Incorrect |
12 ms |
41564 KB |
Output isn't correct |
| 24 |
Incorrect |
11 ms |
41712 KB |
Output isn't correct |
| 25 |
Incorrect |
131 ms |
47956 KB |
Output isn't correct |
| 26 |
Incorrect |
289 ms |
51028 KB |
Output isn't correct |
| 27 |
Incorrect |
488 ms |
54624 KB |
Output isn't correct |
| 28 |
Incorrect |
570 ms |
57552 KB |
Output isn't correct |
| 29 |
Incorrect |
643 ms |
58704 KB |
Output isn't correct |
| 30 |
Incorrect |
606 ms |
60612 KB |
Output isn't correct |
