#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using ll = long long;
ll max_range = 500002;
class name {
public:
ll time;
ll pos;
ll value;
bool operator<(const name b) const {
if (time != b.time)
return time < b.time;
return pos < b.pos;
}
};
ll dp[500005];
ll dpleft[500005];
ll dpright[500005];
ll segleft[1100000];
ll segright[1100000];
name a[500005];
ll N, U, D, S;
void change(ll* seg, ll* data, ll pos, ll number, ll left = 1, ll right = max_range, ll i = 1) {
if (left == right) {
seg[i] = pos;
data[pos] = number;
return;
}
ll mid = (left + right) / 2;
if (pos <= mid) {
change(seg, data, pos, number, left, mid, 2 * i);
seg[i] = seg[2 * i + 1];
if (data[seg[i]] < data[seg[2 * i]])
seg[i] = seg[2 * i];
}
else {
change(seg, data, pos, number, mid + 1, right, 2 * i + 1);
seg[i] = seg[2 * i];
if (data[seg[i]] < data[seg[2 * i + 1]]) {
seg[i] = seg[2 * i + 1];
}
}
}
ll get_max_pos(ll* seg, ll* data, ll s, ll e, ll left = 1, ll right = max_range, ll i = 1) {
if (right < left)
return 0;
if (left >= s && right <= e) {
return seg[i];
}
if (left > e || right < s) {
return 0;
}
ll mid = (right + left) / 2;
ll get1 = get_max_pos(seg, data, s, e, left, mid, 2 * i);
ll get2 = get_max_pos(seg, data, s, e, mid + 1, right, 2 * i + 1);
if (data[get1] > data[get2])
return get1;
return get2;
}
ll set_up(ll* seg, ll* data, ll left = 1, ll right = max_range, ll i = 1) {
if (left == right) {
seg[i] = left;
return seg[i];
}
ll mid = (left + right) / 2;
ll get1 = set_up(seg, data, left, mid, 2 * i);
ll get2 = set_up(seg, data, mid + 1, right, 2 * i + 1);
if (data[get1] > data[get2])
seg[i] = seg[2 * i];
else seg[i] = seg[2 * i + 1];
return seg[i];
}
void func(ll start, ll end) {
if (end - start == 1) {
ll pos = a[start].pos;
ll value = a[start].value;
ll max = dp[pos] + value;
ll get1 = get_max_pos(segright, dpright, 1, pos - 1);
ll get2 = get_max_pos(segleft, dpleft, pos + 1, max_range);
max = std::max(max , dp[get1] - std::abs(get1 - pos) * D + value);
max = std::max(max, dp[get2] - std::abs(get2 - pos) * U + value);
dp[pos] = max;
change(segleft, dpleft, pos, dp[pos] - pos * U);
change(segright, dpright, pos, dp[pos] - (max_range - pos) * D);
}
else {
std::vector<ll> changing_number;
for (ll q = start; q < end; q++) {
ll pos = a[q].pos;
ll value = a[q].value;
ll max = dp[pos] + value;
ll get1 = get_max_pos(segright, dpright, 1, pos - 1);
ll get2 = get_max_pos(segleft, dpleft, pos + 1, max_range);
max = std::max(max, dp[get1] - std::abs(get1 - pos) * D + value);
max = std::max(max, dp[get2] - std::abs(get2 - pos) * U + value);
changing_number.push_back(max);
}
for (ll q = 0; q < changing_number.size(); q++) {
ll pos = a[q + start].pos;
dp[pos] = changing_number[q];
}
std::vector<ll> u1;
std::vector<ll> u2;
ll prev_max = changing_number[0];
u1.push_back(prev_max);
for (ll q = start + 1; q < end; q++) {
ll pos = a[q].pos;
ll value = a[q].value;
ll max = dp[pos];
ll get1 = get_max_pos(segright, dpright, a[q - 1].pos + 1, pos - 1);
if(std::abs(pos - a[q-1].pos) > 1)
max = std::max(max, dp[get1] - std::abs(pos - get1) * D + value);
max = std::max(max, prev_max - std::abs(pos - a[q - 1].pos) * D + value);
u1.push_back(max);
prev_max = max;
}
prev_max = changing_number.back();
u2.push_back(prev_max);
for (ll q = end - 2; q >= start; q--) {
ll pos = a[q].pos;
ll value = a[q].value;
ll max = dp[pos];
ll get1 = get_max_pos(segleft, dpleft, pos + 1, a[q + 1].pos - 1);
if(std::abs(a[q + 1].pos -pos) > 1)
max = std::max(max, dp[get1] - std::abs(get1 - pos) * U + value);
max = std::max(max, prev_max - std::abs(a[q + 1].pos - pos) * U + value);
u2.push_back(max);
prev_max = max;
}
for (ll q = 0; q < u1.size(); q++) {
ll pos = a[start + q].pos;
dp[pos] = std::max(u1[q], u2[u2.size() - q - 1]);
change(segleft, dpleft, pos, dp[pos] - pos * U);
change(segright, dpright, pos, dp[pos] - (max_range - pos) * D);
}
}
}
int main() {
std::cin.sync_with_stdio(false);
std::cin.tie(0);
std::cin >> N >> U >> D >> S;
for (ll q = 0; q < N; q++) {
std::cin >> a[q].time >> a[q].pos >> a[q].value;
}
std::sort(&a[0], &a[N]);
// let 0 position be the worst case as much as possible
dp[0] = -100000000000000000ll;
dpleft[0] = -100000000000000000ll;
dpright[0] = -100000000000000000ll;
for (ll q = 1; q <= max_range; q++) {
if (q < S) {
dp[q] = std::abs(q - S) * -U;
}
else if (q > S) {
dp[q] = std::abs(q - S) * -D;
}
}
for (ll q = 1; q <= max_range; q++) {
dpleft[q] = dp[q] - U * q;
dpright[q] = dp[q] - (max_range - q) * D;
}
set_up(segleft, dpleft);
set_up(segright, dpright);
ll start = 0;
ll end = 0;
while (end != N) {
while (a[start].time == a[end].time) {
++end;
if (end == N)
break;
}
func(start, end);
start = end;
}
ll result = 0;
for (ll q = 1; q <= max_range; q++) {
if (q < S) {
result = std::max(result, dp[q] - std::abs(q - S) * D);
}
else if (q == S) {
result = std::max(result, dp[q]);
}
else {
result = std::max(result, dp[q] - std::abs(q - S) * U);
}
}
std::cout << result;
return 0;
}
Compilation message
salesman.cpp: In function 'void func(ll, ll)':
salesman.cpp:101:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | for (ll q = 0; q < changing_number.size(); q++) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:133:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | for (ll q = 0; q < u1.size(); q++) {
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
28524 KB |
Output is correct |
| 2 |
Correct |
26 ms |
28524 KB |
Output is correct |
| 3 |
Correct |
27 ms |
28524 KB |
Output is correct |
| 4 |
Correct |
28 ms |
28524 KB |
Output is correct |
| 5 |
Correct |
33 ms |
28652 KB |
Output is correct |
| 6 |
Correct |
73 ms |
29036 KB |
Output is correct |
| 7 |
Correct |
160 ms |
29744 KB |
Output is correct |
| 8 |
Correct |
293 ms |
30832 KB |
Output is correct |
| 9 |
Correct |
417 ms |
32180 KB |
Output is correct |
| 10 |
Correct |
624 ms |
35692 KB |
Output is correct |
| 11 |
Correct |
834 ms |
35616 KB |
Output is correct |
| 12 |
Correct |
1086 ms |
38084 KB |
Output is correct |
| 13 |
Correct |
1085 ms |
38088 KB |
Output is correct |
| 14 |
Correct |
1295 ms |
40304 KB |
Output is correct |
| 15 |
Correct |
929 ms |
40312 KB |
Output is correct |
| 16 |
Correct |
1369 ms |
40304 KB |
Output is correct |
| 17 |
Correct |
26 ms |
28524 KB |
Output is correct |
| 18 |
Correct |
26 ms |
28524 KB |
Output is correct |
| 19 |
Correct |
30 ms |
28524 KB |
Output is correct |
| 20 |
Correct |
34 ms |
28524 KB |
Output is correct |
| 21 |
Correct |
31 ms |
28524 KB |
Output is correct |
| 22 |
Correct |
36 ms |
28652 KB |
Output is correct |
| 23 |
Correct |
36 ms |
28652 KB |
Output is correct |
| 24 |
Correct |
36 ms |
28652 KB |
Output is correct |
| 25 |
Correct |
433 ms |
31104 KB |
Output is correct |
| 26 |
Correct |
710 ms |
34000 KB |
Output is correct |
| 27 |
Correct |
1133 ms |
39364 KB |
Output is correct |
| 28 |
Correct |
1278 ms |
38212 KB |
Output is correct |
| 29 |
Correct |
1802 ms |
40928 KB |
Output is correct |
| 30 |
Correct |
1622 ms |
43160 KB |
Output is correct |
