#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
typedef long long ll;
const int NMAX = 5e5 + 5;
ll n, d, u, s, x, m, t, base = 1, ans, dp[NMAX];
ll seg1[1 << 20], seg2[1 << 20];
vector<pair<ll, ll>> v[NMAX];
void upd1(int idx, ll v) {
idx += base;
while (idx) {
seg1[idx] = max(seg1[idx], v);
idx /= 2;
}
return;
}
void upd2(int idx, ll v) {
idx += base;
while (idx) {
seg2[idx] = max(seg2[idx], v);
idx /= 2;
}
return;
}
ll mx1(int l, int r) {
ll ret = -1e18;
l += base; r += base;
while (l <= r) {
if (l & 1) ret = max(ret, seg1[l++]);
if (!(r & 1)) ret = max(ret, seg1[r--]);
l /= 2; r /= 2;
}
return ret;
}
ll mx2(int l, int r) {
ll ret = -1e18;
l += base; r += base;
while (l <= r) {
if (l & 1) ret = max(ret, seg2[l++]);
if (!(r & 1)) ret = max(ret, seg2[r--]);
l /= 2; r /= 2;
}
return ret;
}
int main(void) {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> u >> d >> s;
for (int i = 0; i < n; i++) {
cin >> t >> x >> m;
v[t].emplace_back(x, m);
}
base = 1 << 19;
for (int i = 1; i < base * 2; i++) seg1[i] = seg2[i] = -1e18;
dp[s] = 0; upd1(s, d * s); upd2(s, -u * s);
for (int t = 0; t < NMAX; t++) {
if (v[t].empty()) continue;
sort(all(v[t]));
for (auto& [x, m] : v[t]) {
dp[x] = max(-d * x + mx1(0, x - 1), u * x + mx2(x + 1, base - 1));
upd1(x, d * x + dp[x]); upd2(x, -u * x + dp[x]);
}
for (auto& [x, m] : v[t]) {
dp[x] = -d * x + mx1(0, x) + m;
upd1(x, d * x + dp[x]);
}
for (int i = v[t].size() - 1; i >= 0; i--) {
auto& [x, m] = v[t][i];
ll y = u * x + mx2(x, base - 1) + m;
dp[x] = max(dp[x], y);
upd2(x, -u * x + y);
}
for (auto& [x, m] : v[t]) {
upd1(x, d * x + dp[x]); upd2(x, -u * x + dp[x]);
if (x > s) ans = max(ans, -u * (x - s) + dp[x]);
else ans = max(ans, -d * (s - x) + dp[x]);
}
}
cout << ans;
return 0;
}
Compilation message
salesman.cpp: In function 'int main()':
salesman.cpp:68:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
68 | for (auto& [x, m] : v[t]) {
| ^
salesman.cpp:73:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
73 | for (auto& [x, m] : v[t]) {
| ^
salesman.cpp:78:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
78 | auto& [x, m] = v[t][i];
| ^
salesman.cpp:83:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
83 | for (auto& [x, m] : v[t]) {
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
16 ms |
28372 KB |
Output is correct |
| 2 |
Correct |
15 ms |
28432 KB |
Output is correct |
| 3 |
Correct |
15 ms |
28500 KB |
Output is correct |
| 4 |
Correct |
19 ms |
28520 KB |
Output is correct |
| 5 |
Correct |
24 ms |
28592 KB |
Output is correct |
| 6 |
Correct |
44 ms |
32896 KB |
Output is correct |
| 7 |
Correct |
92 ms |
33940 KB |
Output is correct |
| 8 |
Correct |
148 ms |
35456 KB |
Output is correct |
| 9 |
Correct |
237 ms |
37156 KB |
Output is correct |
| 10 |
Correct |
353 ms |
41768 KB |
Output is correct |
| 11 |
Correct |
455 ms |
41800 KB |
Output is correct |
| 12 |
Correct |
562 ms |
44940 KB |
Output is correct |
| 13 |
Correct |
610 ms |
44964 KB |
Output is correct |
| 14 |
Correct |
693 ms |
48032 KB |
Output is correct |
| 15 |
Correct |
616 ms |
48152 KB |
Output is correct |
| 16 |
Correct |
774 ms |
47928 KB |
Output is correct |
| 17 |
Correct |
14 ms |
28372 KB |
Output is correct |
| 18 |
Correct |
15 ms |
28460 KB |
Output is correct |
| 19 |
Correct |
15 ms |
28452 KB |
Output is correct |
| 20 |
Correct |
17 ms |
28500 KB |
Output is correct |
| 21 |
Correct |
18 ms |
28500 KB |
Output is correct |
| 22 |
Correct |
18 ms |
28644 KB |
Output is correct |
| 23 |
Correct |
19 ms |
28652 KB |
Output is correct |
| 24 |
Correct |
18 ms |
28648 KB |
Output is correct |
| 25 |
Correct |
152 ms |
34540 KB |
Output is correct |
| 26 |
Correct |
223 ms |
36500 KB |
Output is correct |
| 27 |
Correct |
346 ms |
39144 KB |
Output is correct |
| 28 |
Correct |
436 ms |
39160 KB |
Output is correct |
| 29 |
Correct |
601 ms |
41584 KB |
Output is correct |
| 30 |
Correct |
514 ms |
42352 KB |
Output is correct |
