Submission #600143

#	Time	Username	Problem	Language	Result	Execution time	Memory
600143		dooompy	Salesman (IOI09_salesman)	C++17	0 / 100	221 ms	65536 KiB

salesman

#include "bits/stdc++.h"

using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

using ll = long long;

struct fair {
    int t, l, m;

    bool operator<(fair o) const {
        if (t == o.t) {
            return l < o.l;
        }
        return t < o.t;
    }
};

vector<fair> fairs;

struct node {
    int l, r, val;
    node *lc, *rc;

    node(int _l, int _r) : l(_l), r(_r) {
        if (l == r) {
            val = INT_MIN/2;
            return;
        }
        int mid = (l + r) / 2;

        lc = new node(l, mid);
        rc = new node(mid + 1, r);

        val = max(lc->val, rc->val);
    }

    void set(int loc, int nv) {
        if (loc == l) {
            val = nv;
            return;
        }

        int mid = (l + r) / 2;
        if (loc <= mid) {
            lc->set(loc, nv);
        } else rc->set(loc, nv);

        val = max(lc->val, rc->val);
    }

    int query(int ql, int qr) {
        if (ql <= l && r <= qr) return val;
        if (l > qr || r < ql) return INT_MIN/2;

        return max(lc->query(ql, qr), rc->query(ql, qr));
    }
};

int n, u, d, s;

int cost(int a, int b) {
    if (a == b) return 0;
    if (a < b) {
        return (b-a) * d;
    } else return (a-b) * u;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("salesman.in", "r", stdin);
//    freopen("salesman.out", "w", stdout);
    cin >> n >> u >> d >> s;

    for (int i = 0; i < n; i++) {
        int t, l, m; cin >> t >> l >> m;
        fairs.push_back({t, l, m});
    }

    sort(fairs.begin(), fairs.end());

    vector<int> equal;
    int ct = 1;
    for (int i = 0; i < n; i++) {
        if (i == n-1) {
            equal.push_back(ct);
            continue;
        }

        if (fairs[i].t != fairs[i+1].t) {
            equal.push_back(ct); ct = 1;
        } else {
            ct++;
        }
    }

    node *up = new node(1, 500001);
    node *down = new node(1, 500001);

    up->set(s, -u*s); down->set(s, d*s);

    int id = 0;
    for (int i = 0; i < n;) {
        int ub = i + equal[id];

        vector<int> curmax(equal[id]);
        vector<int> lhmax(equal[id]);
        vector<int> hlmax(equal[id]);

        for (int j = i; j < ub; j++) {
            curmax[j-i] = max(up->query(fairs[j].l, 500001) + fairs[j].l*u, down->query(1, fairs[j].l) - fairs[j].l*d) + fairs[j].m;
        }

        for (int j = i; j < ub; j++) {
            if (i == j) lhmax[0] = curmax[0];
            else {
                lhmax[j-i] = curmax[j-i];
                lhmax[j-i] = max(lhmax[j-i], lhmax[j-i-1] - cost(fairs[j-1].l, fairs[j].l) + fairs[j].m);
            }
        }

        for (int j = ub-1; j >= i; j--) {
            if (j == ub-1) hlmax[j-i] = curmax[j-i];
            else {
                hlmax[j-i] = curmax[j-i];
                hlmax[j-i] = max(hlmax[j-i], hlmax[j-i+1] - cost(fairs[j+1].l, fairs[j].l) + fairs[j].m);
            }
        }

        for (int j = i; j < ub; j++) {
            curmax[j-i] = max({curmax[j-i], hlmax[j-i], lhmax[j-i]});
        }

        for (int j = i; j < ub; j++) {
            up->set(fairs[j].l, curmax[j-i] - u*fairs[j].l);
            down->set(fairs[j].l, curmax[j-i] + d * fairs[j].l);
        }

        i = ub; id++;
    }

    int ans = max(down->query(1, s) - s*d, up->query(s, 500001) + s*u);

    cout << max(ans, 0) << endl;

//    cout << equal;


}

• Subtask 1: 0 / 100