제출 #1149623

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1149623		Bungmint	Salesman (IOI09_salesman)	C++20	100 / 100	1167 ms	35176 KiB

salesman

// Copyright © 2024 Youngmin Park. All rights reserved.
// #pragma GCC optimize("O3")
// #pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;

#pragma region TEMPLATE

using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
using vpi = vector<pii>;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vpl = vector<pll>;
using ld = long double;
template <typename T, size_t SZ>
using ar = array<T, SZ>;
template <typename T>
using pqg = priority_queue<T, vector<T>, greater<T>>;

#define all(v) (v).begin(), (v).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound

constexpr ll LINF = 1e18;
const ld PI = acos((ld)-1.0);
constexpr int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>
constexpr bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template <typename T>
constexpr bool ckmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); }  // divide a by b rounded up
ll fdiv(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); }  // divide a by b rounded down

#ifdef LOCAL
#include "miscellaneous/debug.h"
#else
#define dbg(...) 42
#endif

#pragma endregion TEMPLATE

constexpr ll NEG_INF = -LINF;

struct Info {
    ll dp_d, dp_u;
    Info(ll dpd = NEG_INF, ll dpu = NEG_INF) : dp_d(dpd), dp_u(dpu) {}
    Info operator+(const Info &other) const {
        if (dp_d == NEG_INF) return other;
        if (other.dp_d == NEG_INF) return *this;
        return {max(dp_d, other.dp_d), max(dp_u, other.dp_u)};
    }
};

constexpr int MAXN = 1 << 19;
ll tmp1[MAXN], tmp2[MAXN];
Info seg[2 * MAXN];
ll dp[MAXN];
int N, U, D, S;

void upd_assign(int i, const Info &v, int x, int l, int r) {
    if (r - l == 1) {
        seg[x] = v;
        return;
    }
    int mid = (l + r) / 2;
    if (i < mid) {
        upd_assign(i, v, 2 * x + 1, l, mid);
    } else
        upd_assign(i, v, 2 * x + 2, mid, r);
    seg[x] = seg[2 * x + 1] + seg[2 * x + 2];
}
void upd_assign(int i, const Info &v) {
    upd_assign(i, v, 0, 0, MAXN);
}
void upd(int i, const Info &v, int x, int l, int r) {
    if (r - l == 1) {
        seg[x] = seg[x] + v;
        return;
    }
    int mid = (l + r) / 2;
    if (i < mid) {
        upd(i, v, 2 * x + 1, l, mid);
    } else
        upd(i, v, 2 * x + 2, mid, r);
    seg[x] = seg[2 * x + 1] + seg[2 * x + 2];
}
void upd(int i, const Info &v) {
    upd(i, v, 0, 0, MAXN);
}
Info query(int ql, int qr, int x, int xl, int xr) {
    if (ql <= xl && xr <= qr) {
        return seg[x];
    }
    if (ql >= xr || xl >= qr) return Info();
    int mid = (xl + xr) / 2;
    Info lef = query(ql, qr, 2 * x + 1, xl, mid);
    Info rig = query(ql, qr, 2 * x + 2, mid, xr);
    return lef + rig;
}
Info query(int ql, int qr) {
    return query(ql, qr, 0, 0, MAXN);
}

// going upstream U, downstream D
// starting point - upstream
// dp(i, j)
// same day markets
// go all the way to the left and right right right?
// XOOOO
// go left to right
// go right to left
// dp(i) = val_i + max(max_{j <= i}(dp(j) - D(i - j)), max_{j > i}(dp(j) - U(j - i)))
// max(dp(j) - Dj), max(dp(j) + Uj)

void solve() {
    cin >> N >> U >> D >> S;
    vector<ar<int, 3>> events(N);
    for (auto &[t, l, profit] : events) cin >> t >> l >> profit;
    sort(all(events));
    for (int i = 0; i < MAXN; i++) {
        dp[i] = NEG_INF;
    }
    upd(S, Info(D * S, -U * S));
    dp[S] = 0;
    dbg(query(S, S + 1).dp_d);
    for (int i = 0; i < N; i++) {
        vi todo = {i};
        while (i + 1 < N && events[i][0] == events[i + 1][0]) {
            i++;
            todo.pb(i);
        }
        // -->
        dbg(todo);
        for (auto &id : todo) {
            auto [t, l, profit] = events[id];
            tmp1[l] = dp[l];
            Info lef = query(1, l + 1);
            Info rig = query(l + 1, MAXN);
            ckmax(tmp1[l], profit + max(lef.dp_d - D * l, rig.dp_u + U * l));
            dbg(i, l, tmp1[l]);
            upd(l, Info(tmp1[l] + D * l, tmp1[l] - U * l));
        }
        for (auto &id : todo) {
            auto [t, l, profit] = events[id];
            upd_assign(l, Info(dp[l] + D * l, dp[l] - U * l));
        }
        reverse(all(todo));
        for (auto &id : todo) {
            auto [t, l, profit] = events[id];
            tmp2[l] = dp[l];
            Info lef = query(1, l + 1);
            Info rig = query(l + 1, MAXN);
            ckmax(tmp2[l], profit + max(lef.dp_d - D * l, rig.dp_u + U * l));
            upd(l, Info(tmp2[l] + D * l, tmp2[l] - U * l));
        }
        for (auto &id : todo) {
            auto [t, l, profit] = events[id];
            upd(l, Info(tmp1[l] + D * l, tmp1[l] - U * l));
        }
    }
    Info lef = query(1, S + 1);
    Info rig = query(S + 1, MAXN);
    dbg(lef.dp_d);
    int ans = max(lef.dp_d - D * S, rig.dp_u + U * S);
    std::cout << ans << '\n';
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    int testcase = 1;
    // cin >> testcase;
    while (testcase--) {
        solve();
    }
#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * (double)clock() / CLOCKS_PER_SEC << " s.\n";
#endif
}

• Subtask 1: 100 / 100