Submission #505121

#	Time	Username	Problem	Language	Result	Execution time	Memory
505121		blue	Salesman (IOI09_salesman)	C++17	100 / 100	591 ms	44220 KiB

salesman

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using ll = long long;
const int mx = 500'001;
const ll INF = 1'000'000'000'000'000'000LL;
using vll = vector<ll>;
#define sz(x) int(x.size())

struct fair
{
    ll l;
    ll m;
};

bool operator < (fair A, fair B)
{
    return A.l < B.l;
}




vector<fair> F[1+mx];


const int Z = (1<<19);

struct segtree
{
    vll val = vll(Z<<1, -INF);

    void update(int I, ll V)
    {
        val[Z+I] = max(val[Z+I], V);
        for(int i = (Z+I)>>1; i >= 1; i >>= 1)
            val[i] = max(val[2*i], val[2*i+1]);
    }

    ll rangemax(ll L, ll R)
    {
        L += Z;
        R += Z+1;
        ll ans = -INF;
        while(L < R)
        {
            if(L & 1)
            {
                ans = max(ans, val[L]);
                L++;
            }
            if(R & 1)
            {
                R--;
                ans = max(ans, val[R]);
            }
            L >>= 1;
            R >>= 1;
        }
        return ans;
    }
};



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    ll U, D;
    ll S;
    cin >> N >> U >> D >> S;

    for(int i = 1; i <= N; i++)
    {
        ll t, l, m;
        cin >> t >> l >> m;
        F[t].push_back({l, m});
    }
    F[mx].push_back({S, 0});

    for(int t = 1; t <= mx; t++) sort(F[t].begin(), F[t].end());

    segtree goleft, goright;
    goleft.update(S, -U*S + 0);
    goright.update(S, +D*S + 0);

    for(int t = 1; t <= mx; t++)
    {
        int q = sz(F[t]);
        if(q == 0) continue;
        vll dp(q);
        for(int i = 0; i < q; i++)
        {
            dp[i] = max(goleft.rangemax(F[t][i].l, mx) + F[t][i].l*U, goright.rangemax(1, F[t][i].l) - F[t][i].l * D);
        }
        for(int i = 1; i < q; i++)
        {
            dp[i] = max(dp[i], dp[i-1]  - D * (F[t][i].l - F[t][i-1].l));
        }
        for(int i = q-2; i >= 0; i--)
        {
            dp[i] = max(dp[i], dp[i+1] - U*(F[t][i+1].l - F[t][i].l));
        }

        vll dpl = dp, dpr = dp;

        dpl[0] = dp[0] + F[t][0].m;
        for(int i = 1; i < q; i++)
        {
            dpl[i] = max(dp[i], dpl[i-1] - D * (F[t][i].l - F[t][i-1].l)) + F[t][i].m;
        }

        dpr[q-1] = dp[q-1] + F[t][q-1].m;
        for(int i = q-2; i >= 0; i--)
        {
            dpr[i] = max(dpr[i], dpr[i+1] - U * (F[t][i+1].l - F[t][i].l)) + F[t][i].m;
        }

        for(int i = 0; i < q; i++)
        {
            goleft.update(F[t][i].l, max(dpl[i], dpr[i]) - U*F[t][i].l);
            goright.update(F[t][i].l, max(dpl[i], dpr[i]) + D*F[t][i].l);
        }
        // for(int i = 1; i < q; i++)
        // {
        //     dp[i] = max(dp[i], dp[i-1] + )
        // }

    }

    cout << goright.rangemax(S, S) - D*S << '\n';
}

• Subtask 1: 100 / 100