#include <bits/stdc++.h>
using namespace std;
#define N 500005
#define inf 2000000005
set<pair<int, int>> in;
int n, u, d, s, t, l, m;
vector<pair<int, int>> fair[N];
int dis(int f, int t) { return f <= t ? (t - f) * d : (f - t) * u; }
int query(int loc) {
int res1, res2;
auto it = in.lower_bound({loc, -inf});
res1 = it == in.end() ? -inf : it->second - dis(it->first, loc);
res2 = it == in.begin() ? -inf : (--it)->second - dis(it->first, loc);
return max(res1, res2);
}
void update(int loc, int val) {
if (query(loc) >= val) return;
auto it = in.insert({loc, val}).first;
it++;
while (it != in.end() && it->second <= val - dis(loc, it->first))
it = in.erase(it);
it--;
while (it != in.begin() && (--it)->second <= val - dis(loc, it->first))
it = in.erase(it);
}
vector<pair<int, int>> tmp;
int main() {
scanf("%d%d%d%d", &n, &u, &d, &s);
for (int i = 1; i <= n; i++) {
scanf("%d%d%d", &t, &l, &m);
fair[t].push_back({l, m});
}
update(s, 0);
int sz;
for (int i = 1; i < N; i++) {
sz = fair[i].size();
if (sz == 0) continue;
tmp.clear();
sort(fair[i].begin(), fair[i].end());
for (int j = 0; j < sz; j++) {
int res = fair[i][j].second + query(fair[i][j].first);
tmp.push_back({res, res});
}
for (int j = 1; j < sz; j++)
tmp[j].first =
max(tmp[j].first, tmp[j - 1].first -
dis(fair[i][j - 1].first, fair[i][j].first) +
fair[i][j].second);
for (int j = sz - 2; j >= 0; j--)
tmp[j].second =
max(tmp[j].second, tmp[j + 1].second -
dis(fair[i][j + 1].first, fair[i][j].first) +
fair[i][j].second);
for (int j = 0; j < sz; j++)
update(fair[i][j].first, max(tmp[j].first, tmp[j].second));
}
printf("%d", query(s));
}
Compilation message
salesman.cpp: In function 'int main()':
salesman.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &n, &u, &d, &s);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &t, &l, &m);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
12024 KB |
Output is correct |
2 |
Correct |
15 ms |
12024 KB |
Output is correct |
3 |
Correct |
15 ms |
12152 KB |
Output is correct |
4 |
Correct |
15 ms |
12152 KB |
Output is correct |
5 |
Correct |
19 ms |
12280 KB |
Output is correct |
6 |
Correct |
32 ms |
12664 KB |
Output is correct |
7 |
Correct |
69 ms |
13788 KB |
Output is correct |
8 |
Correct |
125 ms |
15372 KB |
Output is correct |
9 |
Correct |
193 ms |
16760 KB |
Output is correct |
10 |
Correct |
352 ms |
22604 KB |
Output is correct |
11 |
Correct |
360 ms |
21496 KB |
Output is correct |
12 |
Correct |
511 ms |
24928 KB |
Output is correct |
13 |
Correct |
503 ms |
24872 KB |
Output is correct |
14 |
Correct |
560 ms |
27736 KB |
Output is correct |
15 |
Correct |
657 ms |
29764 KB |
Output is correct |
16 |
Correct |
654 ms |
27876 KB |
Output is correct |
17 |
Correct |
15 ms |
12024 KB |
Output is correct |
18 |
Correct |
16 ms |
12140 KB |
Output is correct |
19 |
Correct |
16 ms |
12024 KB |
Output is correct |
20 |
Correct |
17 ms |
12024 KB |
Output is correct |
21 |
Correct |
16 ms |
12148 KB |
Output is correct |
22 |
Correct |
17 ms |
12152 KB |
Output is correct |
23 |
Correct |
17 ms |
12152 KB |
Output is correct |
24 |
Correct |
18 ms |
12152 KB |
Output is correct |
25 |
Correct |
63 ms |
13048 KB |
Output is correct |
26 |
Correct |
166 ms |
14600 KB |
Output is correct |
27 |
Correct |
224 ms |
17096 KB |
Output is correct |
28 |
Correct |
341 ms |
17004 KB |
Output is correct |
29 |
Correct |
375 ms |
17080 KB |
Output is correct |
30 |
Correct |
287 ms |
18672 KB |
Output is correct |