Submission #1043384

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043384		Sharky	Salesman (IOI09_salesman)	C++17	100 / 100	630 ms	61008 KiB

salesman

// 如果我不曾見過太陽，那我便可以忍受黑暗。
// 但那光照亮新的原野，將我心中的荒蕪造就。

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 500005;
const int INF = 1e14;
const int M = 500001;

vector<array<int, 3>> A[N]; // capital letter :o
int n, u, d, s, dp[N], dp2[N], ans = 0;

struct SegTree {
    int size = 1;
    vector<array<int, 2>> seg;
    void init(int _n) {
        while (size < _n) size *= 2;
        seg.assign(2 * size + 10, {-INF, -INF});
    }
    void update(int pos, int val, int l, int r, int id) {
        if (l == r) {
            seg[id][0] = val - pos * u;
            seg[id][1] = val + pos * d;
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid) update(pos, val, l, mid, id * 2);
        else update(pos, val, mid + 1, r, id * 2 + 1);
        seg[id][0] = max(seg[id * 2][0], seg[id * 2 + 1][0]);
        seg[id][1] = max(seg[id * 2][1], seg[id * 2 + 1][1]);
    }
    int query(int f, int ql, int qr, int l, int r, int id) {
        if (qr < l || r < ql) return -INF;
        if (ql <= l && r <= qr) return seg[id][f];
        int mid = (l + r) >> 1;
        return max(query(f, ql, qr, l, mid, id * 2), query(f, ql, qr, mid + 1, r, id * 2 + 1));
    }
} ST;

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> u >> d >> s;
    for (int i = 1, ti, loc, money; i <= n; i++) {
        cin >> ti >> loc >> money;
        A[ti].push_back({loc, money, i});
        dp[i] = dp2[i] = -INF;
    }
    ST.init(M + 1);
    ST.update(s, 0, 1, M, 1);
    dp[0] = dp2[0] = 0;
    for (int i = 0; i < N; i++) sort(A[i].begin(), A[i].end(), [] (auto a, auto b) { return a[0] < b[0]; });
    for (int i = 1; i <= M; i++) {
        for (auto& [loc, money, id] : A[i]) {
            dp[id] = max({dp[id], ST.query(1, 1, loc - 1, 1, M, 1) - loc * d + money, ST.query(0, loc + 1, M, 1, M, 1) + loc * u + money});
            ST.update(loc, dp[id], 1, M, 1);
        }
        for (auto& [loc, money, id] : A[i]) ST.update(loc, -INF, 1, M, 1);
        reverse(A[i].begin(), A[i].end());
        for (auto& [loc, money, id] : A[i]) {
            dp2[id] = max({dp2[id], ST.query(0, loc + 1, M, 1, M, 1) + loc * u + money, ST.query(1, 1, loc - 1, 1, M, 1) - loc * d + money});
            ST.update(loc, dp2[id], 1, M, 1);
            dp[id] = max(dp[id], dp2[id]);
            ans = max(ans, dp[id] - ((s > loc) ? (s - loc) * d : (loc - s) * u));
        }
        for (auto& [loc, money, id] : A[i]) ST.update(loc, dp[id], 1, M, 1);
    }
    cout << ans << '\n';
}

• Subtask 1: 100 / 100