Submission #697981

#	Time	Username	Problem	Language	Result	Execution time	Memory
697981		puppy	Salesman (IOI09_salesman)	C++17	100 / 100	813 ms	48304 KiB

salesman

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf = 1e11;
vector<pair<int, int>> T[500005];
struct maxseg
{
    vector<int> tree;
    int N;
    maxseg(int _N){N = _N; tree.resize(1<<((int)ceil(log2(N+1))+1));}
    int init(int s, int e, int node, vector<int> &arr)
    {
        if(s==e) return tree[node] = arr[s];
        return tree[node] = max(init(s, (s+e)/2, 2*node, arr), init((s+e)/2+1, e, 2*node+1, arr));
    }
    void update(int i, int v)
    {
        upd(1, N, 1, i, v);
    }
    int query(int l, int r)
    {
        return _query(1, N, 1, l, r);
    }
    void upd(int s, int e, int node, int idx, int val)
    {
        if(e<idx||idx<s) return;
        if(s==e){
            tree[node] = max(tree[node], val); return;
        }
        upd(s, (s+e)/2, 2*node, idx, val); upd((s+e)/2+1, e, 2*node+1, idx, val);
        tree[node] = max(tree[2*node],  tree[2*node+1]);
    }
    int _query(int s, int e, int node, int l, int r)
    {
        if(e<l||r<s) return -inf;
        if(l<=s&&e<=r) return tree[node];
        return max(_query(s, (s+e)/2, 2*node, l, r), _query((s+e)/2+1, e, 2*node+1, l, r));
    }
};

signed main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    int N, U, D, S; cin >> N >> U >> D >> S;
    for (int i = 1; i <= N; i++) {
        int t, l, m; cin >> t >> l >> m;
        T[t].push_back(make_pair(l, m));
    }
    vector<int> in(500002, -inf);
    maxseg seg(500001), seg2(500001);
    in[S] = S * D;
    seg.init(1, 500001, 1, in); //dp[i] + i * D
    in[S] = -S * U;
    seg2.init(1, 500001, 1, in); //dp2[i] - i * U
    for (int i = 1; i <= 500000; i++) {
        if (T[i].empty()) continue;
        sort(T[i].begin(), T[i].end());
        int sz = T[i].size();
        vector<int> prf(sz + 1);
        maxseg seg3(sz), seg4(sz);
        vector<int> in(sz, -inf);
        seg3.init(0, sz-1, 1, in);
        seg4.init(0, sz-1, 1, in);
        for (int k = 0; k < sz; k++) {
            int x = T[i][k].first, v = T[i][k].second;
            prf[k+1] = prf[k] + v;
            int nxt = max(seg.query(1, x) - x * D, seg2.query(x, 500001) + x * U);
            seg3.upd(0, sz-1, 1, k, nxt + x * D - prf[k]);
            seg4.upd(0, sz-1, 1, k, nxt - x * U + prf[k+1]);
        }
        for (int k = 0; k < sz; k++) {
            int x = T[i][k].first;
            int nxt = max(seg3._query(0, sz-1, 1, 0, k) - x * D + prf[k+1], seg4._query(0, sz-1, 1, k, sz-1) + x * U - prf[k]);
            seg.update(x, nxt + x * D);
            seg2.update(x, nxt - x * U);
        }
    }
    cout << max(seg.query(1, S) - S * D, seg2.query(S, 500001) + S * U) << '\n';
}

• Subtask 1: 100 / 100