#include <bits/stdc++.h>
using namespace std;
int n, u, d, s, t, p, m;
vector<tuple<int,int,int>> a;
vector<int> tu(1100000), td(1100000);
void update(vector<int> &t, int p, int v) {
for (t[p += 500005]=v; p > 1; p >>= 1) t[p>>1] = max(t[p], t[p^1]);
}
int query(const vector<int> &t, int l, int r) {
int ret = INT32_MIN;
for (l+=500005,r+=500006; l<r; l>>=1,r>>=1) {
if (l&1) ret = max(ret, t[l++]);
if (r&1) ret = max(ret, t[--r]);
}
return ret;
}
int f(int x) {
return max(query(td, 0, x)-d*x, query(tu, x, 500004)+u*x);
}
void up(int p, int di) {
update(tu, p, max(di-u*p, query(tu, p, p)));
update(td, p, max(di+d*p, query(td, p, p)));
}
int main() {
scanf("%d%d%d%d", &n, &u, &d, &s);
for (int i=0;i<n;++i) {
scanf("%d%d%d", &t, &p, &m);
a.push_back({t, p, m});
}
sort(a.begin(), a.end());
for (int i=0;i<500005;++i) {
update(tu, i, -2e9);
update(td, i, -2e9);
}
up(s, 0);
for (int i=0;i<n;++i) {
if (i+1 < n && get<0>(a[i]) == get<0>(a[i+1])) {
auto [t, p, m] = a[i];
vector<tuple<int,int,int>> market;
while (i < n && get<0>(a[i]) == t) market.push_back(a[i++]);
i--;
vector<int> l, r;
for (auto [t, p, m] : market) {
int y = f(p);
l.push_back(y);
r.push_back(y);
}
l[0] += get<2>(market[0]);
r.back() += get<2>(market.back());
for (int j=1;j<market.size();++j)
l[j] = max(l[j], l[j-1] - d*(get<1>(market[j]) - get<1>(market[j-1]))) + get<2>(market[j]);
for (int j=market.size()-2;j>=0;--j)
r[j] = max(r[j], r[j+1] - u*(get<1>(market[j+1]) - get<1>(market[j]))) + get<2>(market[j]);
for (int j=0;j<l.size();++j)
up(get<1>(market[j]), max(l[j], r[j]));
}
else {
auto [t, p, m] = a[i];
up(p, f(p)+m);
}
}
printf("%d", f(s));
}
Compilation message
salesman.cpp: In function 'int main()':
salesman.cpp:51:31: warning: unused variable 't' [-Wunused-variable]
for (auto [t, p, m] : market) {
^
salesman.cpp:51:31: warning: unused variable 'm' [-Wunused-variable]
salesman.cpp:58:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j=1;j<market.size();++j)
~^~~~~~~~~~~~~~
salesman.cpp:62:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j=0;j<l.size();++j)
~^~~~~~~~~
salesman.cpp:46:26: warning: unused variable 'p' [-Wunused-variable]
auto [t, p, m] = a[i];
^
salesman.cpp:46:26: warning: unused variable 'm' [-Wunused-variable]
salesman.cpp:66:26: warning: unused variable 't' [-Wunused-variable]
auto [t, p, m] = a[i];
^
salesman.cpp:31: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:33:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &t, &p, &m);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
35 ms |
8960 KB |
Output is correct |
2 |
Correct |
35 ms |
8960 KB |
Output is correct |
3 |
Correct |
35 ms |
8960 KB |
Output is correct |
4 |
Correct |
36 ms |
8960 KB |
Output is correct |
5 |
Correct |
38 ms |
9216 KB |
Output is correct |
6 |
Correct |
53 ms |
9792 KB |
Output is correct |
7 |
Correct |
87 ms |
10364 KB |
Output is correct |
8 |
Correct |
132 ms |
10992 KB |
Output is correct |
9 |
Correct |
173 ms |
12656 KB |
Output is correct |
10 |
Correct |
281 ms |
15716 KB |
Output is correct |
11 |
Correct |
330 ms |
15720 KB |
Output is correct |
12 |
Correct |
402 ms |
15716 KB |
Output is correct |
13 |
Correct |
408 ms |
15720 KB |
Output is correct |
14 |
Correct |
499 ms |
15716 KB |
Output is correct |
15 |
Correct |
429 ms |
15720 KB |
Output is correct |
16 |
Correct |
520 ms |
15720 KB |
Output is correct |
17 |
Correct |
36 ms |
9088 KB |
Output is correct |
18 |
Correct |
35 ms |
8960 KB |
Output is correct |
19 |
Correct |
36 ms |
8960 KB |
Output is correct |
20 |
Correct |
37 ms |
9088 KB |
Output is correct |
21 |
Correct |
39 ms |
9216 KB |
Output is correct |
22 |
Correct |
39 ms |
9216 KB |
Output is correct |
23 |
Correct |
40 ms |
9216 KB |
Output is correct |
24 |
Correct |
39 ms |
9216 KB |
Output is correct |
25 |
Correct |
122 ms |
11128 KB |
Output is correct |
26 |
Correct |
217 ms |
12652 KB |
Output is correct |
27 |
Correct |
327 ms |
15840 KB |
Output is correct |
28 |
Correct |
365 ms |
15716 KB |
Output is correct |
29 |
Correct |
450 ms |
15716 KB |
Output is correct |
30 |
Correct |
462 ms |
17888 KB |
Output is correct |