#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 5e5 + 5, MAX_POS = 5e5 + 5, INF = 2e9 + 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_POS];
void build(int ind) {
for (int i = 1; i <= 4 * MAX_POS - 5; 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);
}
int 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';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
22876 KB |
Output is correct |
| 2 |
Correct |
3 ms |
22876 KB |
Output is correct |
| 3 |
Correct |
4 ms |
22988 KB |
Output is correct |
| 4 |
Correct |
6 ms |
23132 KB |
Output is correct |
| 5 |
Correct |
9 ms |
23388 KB |
Output is correct |
| 6 |
Correct |
33 ms |
25180 KB |
Output is correct |
| 7 |
Correct |
91 ms |
28424 KB |
Output is correct |
| 8 |
Correct |
182 ms |
33872 KB |
Output is correct |
| 9 |
Correct |
295 ms |
39760 KB |
Output is correct |
| 10 |
Correct |
524 ms |
60752 KB |
Output is correct |
| 11 |
Correct |
601 ms |
61272 KB |
Output is correct |
| 12 |
Runtime error |
385 ms |
65536 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
367 ms |
65536 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
395 ms |
65536 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
380 ms |
65536 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
409 ms |
65536 KB |
Execution killed with signal 9 |
| 17 |
Incorrect |
4 ms |
22876 KB |
Output isn't correct |
| 18 |
Incorrect |
3 ms |
22996 KB |
Output isn't correct |
| 19 |
Incorrect |
4 ms |
22876 KB |
Output isn't correct |
| 20 |
Incorrect |
6 ms |
23036 KB |
Output isn't correct |
| 21 |
Incorrect |
6 ms |
22876 KB |
Output isn't correct |
| 22 |
Incorrect |
9 ms |
23132 KB |
Output isn't correct |
| 23 |
Incorrect |
8 ms |
22876 KB |
Output isn't correct |
| 24 |
Incorrect |
9 ms |
23132 KB |
Output isn't correct |
| 25 |
Incorrect |
142 ms |
23636 KB |
Output isn't correct |
| 26 |
Incorrect |
230 ms |
24404 KB |
Output isn't correct |
| 27 |
Incorrect |
381 ms |
25408 KB |
Output isn't correct |
| 28 |
Incorrect |
438 ms |
27084 KB |
Output isn't correct |
| 29 |
Incorrect |
550 ms |
26192 KB |
Output isn't correct |
| 30 |
Incorrect |
603 ms |
26828 KB |
Output isn't correct |
