# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
511018 |
2022-01-15T04:29:16 Z |
tabr |
Salesman (IOI09_salesman) |
C++17 |
|
703 ms |
27148 KB |
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
struct segtree {
using T = int;
int n;
vector<T> node;
T e() {
return (int) -2e9;
}
T op(T x, T y) {
return max(x, y);
}
segtree() : segtree(0) {}
segtree(int _n) {
if (_n <= 1) {
n = _n;
} else {
n = 1 << (32 - __builtin_clz(_n - 1));
}
node.resize(2 * n, e());
}
segtree(vector<T> v) {
if ((int) v.size() <= 1) {
n = (int) v.size();
} else {
n = 1 << (32 - __builtin_clz((int) v.size() - 1));
}
node.resize(2 * n, e());
for (int i = 0; i < (int) v.size(); i++) {
node[i + n] = v[i];
}
for (int i = n - 1; i > 0; i--) {
node[i] = op(node[2 * i], node[2 * i + 1]);
}
}
void update(int k, T v) {
k += n;
node[k] = v; // update
// node[k] += v; // add
while (k > 1) {
k /= 2;
node[k] = op(node[2 * k], node[2 * k + 1]);
}
}
T get(int x, int y, int k, int l, int r) {
if (r <= x || y <= l) {
return e();
}
if (x <= l && r <= y) {
return node[k];
}
T vl = get(x, y, 2 * k, l, (l + r) / 2);
T vr = get(x, y, 2 * k + 1, (l + r) / 2, r);
return op(vl, vr);
}
T get(int x, int y) {
return get(x, y, 1, 0, n);
}
T get(int x) {
return node[x + n];
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, u, d, s;
cin >> n >> u >> d >> s;
vector<tuple<int, int, int>> a(n);
for (int i = 0; i < n; i++) {
int t, l, m;
cin >> t >> l >> m;
a[i] = make_tuple(t, l, m);
}
sort(a.begin(), a.end());
vector<int> dp(500005, (int) -1e9);
dp[s] = 0;
segtree segu(500005), segd(500005);
segu.update(s, -u * s);
segd.update(s, d * s);
vector<int> c(n);
for (int beg = 0, end = 0; beg < n; beg = end) {
while (end < n && get<0>(a[beg]) == get<0>(a[end])) {
end++;
}
for (int i = beg; i < end; i++) {
auto [t, l, m] = a[i];
c[i] = max(segu.get(l, 500005) + u * l, segd.get(0, l) - d * l);
}
int z = (int) -1e9;
for (int i = beg; i < end; i++) {
auto [t, l, m] = a[i];
z -= d * l;
z = max(z, c[i]);
z += m;
dp[l] = max(dp[l], z);
z += d * l;
}
z = (int) -1e9;
for (int i = end - 1; i >= beg; i--) {
auto [t, l, m] = a[i];
z += u * l;
z = max(z, c[i]);
z += m;
dp[l] = max(dp[l], z);
z -= u * l;
}
for (int i = beg; i < end; i++) {
auto [t, l, m] = a[i];
debug(dp[l], c[i]);
segu.update(l, dp[l] - u * l);
segd.update(l, dp[l] + d * l);
}
}
int ans = 0;
for (int i = 0; i < 500005; i++) {
ans = max(ans, dp[i] - d * max(0, s - i) - u * max(0, i - s));
}
cout << ans << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
10500 KB |
Output is correct |
2 |
Correct |
7 ms |
10444 KB |
Output is correct |
3 |
Correct |
7 ms |
10444 KB |
Output is correct |
4 |
Correct |
13 ms |
10432 KB |
Output is correct |
5 |
Correct |
10 ms |
10528 KB |
Output is correct |
6 |
Correct |
32 ms |
11152 KB |
Output is correct |
7 |
Correct |
63 ms |
12164 KB |
Output is correct |
8 |
Correct |
137 ms |
13756 KB |
Output is correct |
9 |
Correct |
189 ms |
15184 KB |
Output is correct |
10 |
Correct |
317 ms |
19824 KB |
Output is correct |
11 |
Correct |
403 ms |
20536 KB |
Output is correct |
12 |
Correct |
487 ms |
22844 KB |
Output is correct |
13 |
Correct |
532 ms |
23136 KB |
Output is correct |
14 |
Correct |
703 ms |
27148 KB |
Output is correct |
15 |
Correct |
633 ms |
26340 KB |
Output is correct |
16 |
Correct |
702 ms |
26360 KB |
Output is correct |
17 |
Correct |
7 ms |
10444 KB |
Output is correct |
18 |
Correct |
7 ms |
10492 KB |
Output is correct |
19 |
Correct |
7 ms |
10444 KB |
Output is correct |
20 |
Correct |
12 ms |
10456 KB |
Output is correct |
21 |
Correct |
11 ms |
10476 KB |
Output is correct |
22 |
Correct |
14 ms |
10572 KB |
Output is correct |
23 |
Correct |
10 ms |
10572 KB |
Output is correct |
24 |
Correct |
11 ms |
10568 KB |
Output is correct |
25 |
Correct |
134 ms |
13440 KB |
Output is correct |
26 |
Correct |
294 ms |
16408 KB |
Output is correct |
27 |
Correct |
330 ms |
20444 KB |
Output is correct |
28 |
Correct |
347 ms |
21296 KB |
Output is correct |
29 |
Correct |
602 ms |
24852 KB |
Output is correct |
30 |
Correct |
512 ms |
25692 KB |
Output is correct |