#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
const int N = 2000001;
const ll INF = 1e18, MOD = 1e9 + 7, MOD2 = 1e6 + 3;
int n, U, D, s, maxx;
struct SegTree {
vector<int> t;
int start;
void build (int n) {
start = 1;
while (start < n) start <<= 1;
t = vector <int> (2 * start, -2e9);
}
void update (int x, int d) {
x += start;
t[x] = d;
x >>= 1;
while (x) {
t[x] = max (t[2 * x], t[2 * x + 1]);
x >>= 1;
}
}
int get (int l, int r) {
l += start, r += start + 1;
int mx = -2e9;
while (l < r) {
if (l & 1) mx = max (mx, t[l++]);
if (r & 1) mx = max (mx, t[--r]);
l >>= 1, r >>= 1;
}
return mx;
}
} t_left, t_right;
struct shop {
int x, t, m;
bool operator< (shop& b) {
return t < b.t;
}
} a[N];
void process (int l, int r) {
vector <shop> v (a + l, a + r);
vector <int> ans (r - l), ans_l (r - l), ans_r (r - l);
sort (v.begin(), v.end(), [&](shop a, shop b) { return a.x < b.x; });
for (int i = 0; i < v.size (); i++) {
ans[i] = t_left.get (0, v[i].x) - D * v[i].x + v[i].m;
ans[i] = max (ans[i], t_right.get (v[i].x, maxx) + U * v[i].x + v[i].m);
}
ans_l[0] = ans[0], ans_r.back() = ans.back();
for (int i = 1; i < v.size (); i++) {
ans_l[i] = max (ans[i], ans_l[i-1] - D * (v[i].x - v[i-1].x) + v[i].m);
}
for (int i = v.size () - 2; i >= 0; i--) {
ans_r[i] = max (ans[i], ans_r[i+1] - U * (v[i+1].x - v[i].x) + v[i].m);
}
for (int i = 0; i < v.size (); i++) {
ans[i] = max (ans_l[i], ans[i]);
ans[i] = max (ans_r[i], ans[i]);
//cout << v[i].x << ' ' << v[i].t << ' ' << ans[i] << endl;
t_left.update (v[i].x, ans[i] + v[i].x * D);
t_right.update (v[i].x, ans[i] - v[i].x * U);
}
}
int main () {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> U >> D >> s;
for (int i = 0; i < n; i++) {
cin >> a[i].t >> a[i].x >> a[i].m;
maxx = max (maxx, a[i].x);
}
maxx = max (maxx, s);
t_left.build (maxx + 1);
t_right.build (maxx + 1);
t_right.update (s, -s * U);
t_left.update (s, s * D);
sort (a, a + n);
int last = 0;
for (int i = 0; i < n; i++) {
if (a[i].t != a[last].t) {
process (last, i);
last = i;
}
}
process (last, n);
int ans = t_right.get (s, maxx) + U * s;
ans = max (ans, t_left.get (0, s) - D * s);
assert (ans >= 0);
cout << ans;
}
Compilation message
salesman.cpp: In function 'void process(int, int)':
salesman.cpp:70:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<shop>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for (int i = 0; i < v.size (); i++) {
| ~~^~~~~~~~~~~
salesman.cpp:77:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<shop>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for (int i = 1; i < v.size (); i++) {
| ~~^~~~~~~~~~~
salesman.cpp:85:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<shop>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for (int i = 0; i < v.size (); i++) {
| ~~^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
0 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
492 KB |
Output is correct |
4 |
Correct |
2 ms |
492 KB |
Output is correct |
5 |
Correct |
4 ms |
492 KB |
Output is correct |
6 |
Correct |
26 ms |
8812 KB |
Output is correct |
7 |
Correct |
60 ms |
9196 KB |
Output is correct |
8 |
Correct |
112 ms |
9708 KB |
Output is correct |
9 |
Correct |
159 ms |
10476 KB |
Output is correct |
10 |
Correct |
274 ms |
12140 KB |
Output is correct |
11 |
Correct |
326 ms |
12140 KB |
Output is correct |
12 |
Correct |
425 ms |
13420 KB |
Output is correct |
13 |
Correct |
436 ms |
13420 KB |
Output is correct |
14 |
Correct |
580 ms |
14568 KB |
Output is correct |
15 |
Correct |
403 ms |
14444 KB |
Output is correct |
16 |
Correct |
587 ms |
14572 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
2 ms |
492 KB |
Output is correct |
21 |
Correct |
2 ms |
492 KB |
Output is correct |
22 |
Correct |
4 ms |
620 KB |
Output is correct |
23 |
Correct |
3 ms |
620 KB |
Output is correct |
24 |
Correct |
3 ms |
620 KB |
Output is correct |
25 |
Correct |
91 ms |
9836 KB |
Output is correct |
26 |
Correct |
171 ms |
11848 KB |
Output is correct |
27 |
Correct |
280 ms |
14464 KB |
Output is correct |
28 |
Correct |
365 ms |
13660 KB |
Output is correct |
29 |
Correct |
425 ms |
14852 KB |
Output is correct |
30 |
Correct |
444 ms |
16560 KB |
Output is correct |