# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
374433 | 2021-03-07T09:45:35 Z | jhwest2 | Salesman (IOI09_salesman) | C++14 | 1524 ms | 35272 KB |
#include <bits/stdc++.h> #define va first #define vb second using namespace std; typedef long long lint; typedef pair<int, int> pint; typedef pair<lint, lint> plint; const int MAX = 5e5 + 5; const lint INF = 4e18; lint n, u, d, s, Dp[MAX]; pair<plint, lint> A[MAX]; struct SEG { lint T[4 * MAX]; lint init(int lo = 1, int hi = MAX, int idx = 1) { if (lo == hi) return T[idx] = -INF; return T[idx] = max(init(lo, lo + hi >> 1, 2 * idx), init(1 + (lo + hi >> 1), hi, 2 * idx + 1)); } lint update(int a, lint x, int lo = 1, int hi = MAX, int idx = 1) { if (a < lo || a > hi) return T[idx]; if (lo == hi) return T[idx] = x; return T[idx] = max(update(a, x, lo, lo + hi >> 1, 2 * idx), update(a, x, 1 + (lo + hi >> 1), hi, 2 * idx + 1)); } lint query(int a, int b, int lo = 1, int hi = MAX, int idx = 1) { if (b < lo || a > hi) return -INF; if (a <= lo && hi <= b) return T[idx]; return max(query(a, b, lo, lo + hi >> 1, 2 * idx), query(a, b, 1 + (lo + hi >> 1), hi, 2 * idx + 1)); } } S, T; int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin >> n >> u >> d >> s; for (int i = 0; i < n; i++) cin >> A[i].va.va >> A[i].va.vb >> A[i].vb; sort(A, A + n); S.init(); T.init(); S.update(s, d * s); T.update(s, -u * s); int p = 0; for (int day = 1; day < MAX; day++) { vector<int> V; while (p < n && A[p].va.va == day) V.push_back(p++); if (V.empty()) continue; vector<plint> Su, Tu; for (int x : V) { Su.emplace_back(A[x].va.vb, (d + u) * A[x].va.vb + T.query(A[x].va.vb, MAX)); Tu.emplace_back(A[x].va.vb, -(d + u) * A[x].va.vb + S.query(1, A[x].va.vb)); } for (auto x : Su) S.update(x.va, x.vb); for (auto x : Tu) T.update(x.va, x.vb); lint mx = S.query(1, A[V[0]].va.vb) + A[V[0]].vb; for (int i = 0; i < V.size(); i++) { int x = V[i]; if (i) mx = max(mx, S.query(A[x - 1].va.vb + 1, A[x].va.vb)) + A[x].vb; Dp[x] = mx - d * A[x].va.vb; } mx = T.query(A[V.back()].va.vb, MAX) + A[V.back()].vb; for (int i = V.size() - 1; i >= 0; i--) { int x = V[i]; if (i != V.size() - 1) mx = max(mx, T.query(A[x].va.vb, A[x + 1].va.vb - 1)) + A[x].vb; Dp[x] = max(Dp[x], mx + u * A[x].va.vb); } for (int x : V) { S.update(A[x].va.vb, Dp[x] + d * A[x].va.vb); T.update(A[x].va.vb, Dp[x] - u * A[x].va.vb); } } lint ans = 0; for (int i = 0; i < n; i++) { if (A[i].va.vb > s) ans = max(ans, Dp[i] - u * (A[i].va.vb - s)); else ans = max(ans, Dp[i] - d * (s - A[i].va.vb)); } cout << ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 22 ms | 16748 KB | Output is correct |
2 | Correct | 22 ms | 16748 KB | Output is correct |
3 | Correct | 27 ms | 16748 KB | Output is correct |
4 | Correct | 26 ms | 16876 KB | Output is correct |
5 | Correct | 33 ms | 16876 KB | Output is correct |
6 | Correct | 78 ms | 17388 KB | Output is correct |
7 | Correct | 164 ms | 18412 KB | Output is correct |
8 | Correct | 317 ms | 20052 KB | Output is correct |
9 | Correct | 481 ms | 21612 KB | Output is correct |
10 | Correct | 754 ms | 26140 KB | Output is correct |
11 | Correct | 928 ms | 26120 KB | Output is correct |
12 | Correct | 1186 ms | 29336 KB | Output is correct |
13 | Correct | 1210 ms | 29256 KB | Output is correct |
14 | Correct | 1477 ms | 32444 KB | Output is correct |
15 | Correct | 1228 ms | 32492 KB | Output is correct |
16 | Correct | 1509 ms | 32376 KB | Output is correct |
17 | Correct | 22 ms | 16748 KB | Output is correct |
18 | Correct | 22 ms | 16748 KB | Output is correct |
19 | Correct | 33 ms | 16876 KB | Output is correct |
20 | Correct | 26 ms | 16876 KB | Output is correct |
21 | Correct | 27 ms | 16876 KB | Output is correct |
22 | Correct | 36 ms | 17004 KB | Output is correct |
23 | Correct | 32 ms | 17004 KB | Output is correct |
24 | Correct | 33 ms | 17004 KB | Output is correct |
25 | Correct | 302 ms | 20176 KB | Output is correct |
26 | Correct | 632 ms | 24112 KB | Output is correct |
27 | Correct | 972 ms | 30456 KB | Output is correct |
28 | Correct | 1114 ms | 29160 KB | Output is correct |
29 | Correct | 1524 ms | 32956 KB | Output is correct |
30 | Correct | 1359 ms | 35272 KB | Output is correct |