Submission #844831

#	Time	Username	Problem	Language	Result	Execution time	Memory
844831		hamerin	Salesman (IOI09_salesman)	C++17	62 / 100	892 ms	26220 KiB

salesman

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

using li = long long;
using ld = long double;
using pi = pair<int, int>;
using pli = pair<li, li>;

#define all(c) c.begin(), c.end()
#define prec(n) setprecision(n) << fixed

template <typename T>
class SegTree {
   public:
    uint N;
    vector<T> vl;

    explicit SegTree(uint _N) : N(_N), vl(N << 2, numeric_limits<T>::min() / T(2)) {}

    void update(uint s, uint e, uint n, uint t, T x) {
        if (t < s || e < t) return;
        if (s == e) {
            vl[n] = x;
            return;
        }

        uint m = (s + e) >> 1, k = n << 1;
        update(s, m, k, t, x);
        update(m + 1, e, k | 1, t, x);
        vl[n] = max(vl[k], vl[k | 1]);
    }

    T query(uint s, uint e, uint n, uint l, uint r) {
        if (r < s || e < l) return numeric_limits<T>::min() / T(2);
        if (l <= s && e <= r) return vl[n];

        uint m = (s + e) >> 1, k = n << 1;
        return max(query(s, m, k, l, r), query(m + 1, e, k | 1, l, r));
    }

    inline void update(uint t, T x) { update(0, N - 1, 1, t, x); }
    inline T query(uint l, uint r) { return query(0, N - 1, 1, l, r); }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, U, D, S;
    cin >> N >> U >> D >> S;

    vector<int> locs(1, S);
    vector<tuple<int, int, int>> markets;
    markets.emplace_back(0, S, 0);
    markets.emplace_back(500001, S, 0);
    for (int i = 0; i < N; i++) {
        int T, L, M;
        cin >> T >> L >> M;
        markets.emplace_back(T, L, M);
        locs.emplace_back(L);
    }

    sort(all(locs)), locs.erase(unique(all(locs)), locs.end());

    auto get_optimal = [&](const vector<tuple<int, int, int>> &markets) {
        int ret;
        SegTree<int> upper((uint)locs.size()), lower((uint)locs.size());
        for (auto [T, L, M] : markets) {
            const int Lc = lower_bound(all(locs), L) - locs.begin();

            if (T == 0) {
                ret = M;
                upper.update(Lc, -U * L);
                lower.update(Lc, D * L);
                continue;
            }

            ret = max(upper.query(Lc, (uint)locs.size() - 1) + U * L,
                      lower.query(0, Lc) - D * L) +
                  M;
            upper.update(Lc, ret - U * L);
            lower.update(Lc, ret + D * L);
        }

        return ret;
    };


    int res = numeric_limits<int>::min();
    sort(all(markets));
    res = max(res, get_optimal(markets));

    sort(all(markets), [](const tuple<int, int, int> &lhs, const tuple<int, int, int> &rhs) {
        return pi(get<0>(lhs), -get<1>(lhs)) < pi(get<0>(rhs), -get<1>(rhs));
    });
    res = max(res, get_optimal(markets));

    cout << res << '\n';

    return 0;
}

Compilation message (stderr)

salesman.cpp: In lambda function:
salesman.cpp:90:16: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
   90 |         return ret;
      |                ^~~

• Subtask 1: 62 / 100