Submission #861941

#	Time	Username	Problem	Language	Result	Execution time	Memory
861941		12345678	Salesman (IOI09_salesman)	C++17	62 / 100	400 ms	25628 KiB

salesman

#include <bits/stdc++.h>

using namespace std;

const int nx=5e5+5;
int n, u, d, s;
vector<tuple<int, int, int>> v;

struct segtree
{
    int d[4*nx];
    void build(int l, int r, int i)
    {
        if (l==r) return void(d[i]=-2e9);
        int md=(l+r)/2;
        build(l, md, 2*i);
        build(md+1, r, 2*i+1);
        d[i]=max(d[2*i], d[2*i+1]);
    }
    void update(int l, int r, int i, int idx, int vl)
    {
        if (idx<l||r<idx) return;
        if (l==r) return void(d[i]=max(d[i], vl));
        int md=(l+r)/2;
        update(l, md, 2*i, idx, vl);
        update(md+1, r, 2*i+1, idx, vl);
        d[i]=max(d[2*i], d[2*i+1]);
    }
    int query(int l, int r, int i, int ql, int qr)
    {
        if (r<ql||qr<l) return INT_MIN;
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return max(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
    }
} up, dn;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>u>>d>>s;
    v.resize(n);
    for (auto &[x, y, z]:v) cin>>x>>y>>z;
    sort(v.begin(), v.end());
    up.build(1, nx-1, 1); dn.build(1, nx-1, 1);
    up.update(1, nx-1, 1, s, -s*u); dn.update(1, nx-1, 1, s, s*d);
    for (auto [x, y, z]:v)
    {
        int qup=up.query(1, nx-1, 1, y, nx-1);
        int qdn=dn.query(1, nx-1, 1, 1, y);
        int mx=max(qup+y*u, qdn-y*d)+z;
        //printf("%d %d %d %d %d %d\n", x, y, z, qup, qdn, mx);
        up.update(1, nx-1, 1, y, mx-y*u);
        dn.update(1, nx-1, 1, y, mx+y*d);
    }
    //cout<<up.query(1, nx-1, 1, s, nx-1)+s*u<<' '<<dn.query(1, nx-1, 1, 1, s)-s*d<<'\n';
    cout<<max(up.query(1, nx-1, 1, s, nx-1)+s*u, dn.query(1, nx-1, 1, 1, s)-s*d);
}

• Subtask 1: 62 / 100