Submission #511018

#	Time	Username	Problem	Language	Result	Execution time	Memory
511018		tabr	Salesman (IOI09_salesman)	C++17	100 / 100	703 ms	27148 KiB

salesman

#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;
}

• Subtask 1: 100 / 100