제출 #166183

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
166183		dolphingarlic	Salesman (IOI09_salesman)	C++14	52 / 100	1016 ms	57548 KiB

salesman

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

const int MAXN = 5e5 + 1;

struct Node {
    ll up, down, dp;

    Node operator+(Node B) {
        return {max(up, B.up), max(down, B.down), max(dp, B.dp)};
    }
};

struct Fair {
    ll t, l, m;
};
bool operator<(Fair A, Fair B) {
    if (A.t == B.t) return A.l < B.l;
    return A.t < B.t;
}

ll n, u, d, s;
Fair fairs[MAXN];
ll prelims[MAXN], up[MAXN], down[MAXN];

Node segtree[4 * MAXN];
void build(int node = 1, int l = 1, int r = MAXN) {
    if (l == r) {
        if (l == s) segtree[node] = {-l * u, l * d, 0};
        else segtree[node] = {(ll)INT_MIN - l * u, (ll)INT_MIN + l * d, (ll)INT_MIN};
    } else {
        int mid = (l + r) / 2;
        build(node * 2, l, mid);
        build(node * 2 + 1, mid + 1, r);
        segtree[node] = segtree[node * 2] + segtree[node * 2 + 1];
    }
}
void update(int pos, int val, int node = 1, int l = 1, int r = MAXN) {
    if (l == r) {
        segtree[node] = {segtree[node].up - segtree[node].dp + val,
                         segtree[node].down - segtree[node].dp + val, val};
    } else {
        int mid = (l + r) / 2;
        if (pos > mid) update(pos, val, node * 2 + 1, mid + 1, r);
        else update(pos, val, node * 2, l, mid);
        segtree[node] = segtree[node * 2] + segtree[node * 2 + 1];
    }
}
Node query(int a, int b, int node = 1, int l = 1, int r = MAXN) {
    if (l > b || r < a || a > b) return {LLONG_MIN, LLONG_MIN, LLONG_MIN};
    if (l >= a && r <= b) return segtree[node];
    int mid = (l + r) / 2;
    return query(a, b, node * 2, l, mid) + query(a, b, node * 2 + 1, mid + 1, r);
}

inline ll cost(ll from, ll to) {
    if (from > to) return u * (from - to);
    return d * (to - from);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> u >> d >> s;
    FOR(i, 0, n) cin >> fairs[i].t >> fairs[i].l >> fairs[i].m;
    sort(fairs, fairs + n);

    build();
    FOR(i, 0, n) {
        int first = i++;
        while (i < n && fairs[i].l == fairs[first].l) i++;
        int last = --i;

        FOR(j, first, last + 1) {
            Node l = query(1, fairs[j].l), r = query(fairs[j].l + 1, MAXN);
            prelims[j] = max(l.down - fairs[j].l * d, r.up + fairs[j].l * u) + fairs[j].m;
        }

        up[last] = prelims[last];
        for (int j = last - 1; j >= first; j--) {
            up[j] = max(prelims[j], up[j + 1] - cost(fairs[j + 1].l, fairs[j].l) + fairs[j].m);
        }
        down[first] = prelims[first];
        for (int j = first + 1; j <= last; j++) {
            down[j] = max(prelims[j], down[j - 1] - cost(fairs[j - 1].l, fairs[j].l) + fairs[j].m);
        }

        FOR(j, first, last + 1) update(fairs[j].l, max(up[j], down[j]));
    }

    Node l = query(1, s), r = query(s + 1, MAXN);
    cout << max(l.down - s * d, r.up + s * u);
    return 0;
}

• Subtask 1: 52 / 100