Submission #405679

#	Time	Username	Problem	Language	Result	Execution time	Memory
405679		Aldas25	Salesman (IOI09_salesman)	C++14	100 / 100	2102 ms	48160 KiB

salesman

#pragma GCC optimize("O2")

#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(0)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define pb push_back
#define f first
#define s second
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<piii> viii;

const int MAXN = 500100, MAXK = 30;
const ll MOD = 998244353;
const ll INF = 1e17;
const ld PI = asin(1) * 2;

vector<pair<ll, ll>> fairs[MAXN];
int n;
ll u, d;
int s;

ll dp[MAXN];
ll tree[2][4*MAXN];

void build (int tId, int id = 1, int le = 1, int ri = MAXN-1) {
    if (le == ri) {
        tree[tId][id] = -INF;
        return;
    }
    int mid = (le+ri)/2;
    build (tId, 2*id, le, mid);
    build (tId, 2*id+1, mid+1, ri);
    tree[tId][id] = max(tree[tId][2*id], tree[tId][2*id+1]);
}

void upd (int tId, int p, ll x, int id = 1, int le = 1, int ri = MAXN-1) {
    if (le == ri) {
        tree[tId][id] = max(x, tree[tId][id]);
        return;
    }
    int mid = (le+ri)/2;
    if (p <= mid)
        upd (tId, p, x, 2*id, le, mid);
    else
        upd (tId, p, x, 2*id+1, mid+1, ri);
    tree[tId][id] = max(tree[tId][2*id], tree[tId][2*id+1]);
}

ll getMax (int tId, int x, int y, int id = 1, int le = 1, int ri = MAXN-1) {
    if (x > ri || y < le) return -INF;
    if (x <= le && ri <= y) return tree[tId][id];
    int mid = (le+ri)/2;
    return max( getMax(tId, x, y, 2*id, le, mid), getMax(tId, x, y, 2*id+1, mid+1, ri) );
}

void ch (ll l) {
    upd (0, l, dp[l] + l*d);
    upd (1, l, dp[l] - l*u);
}

int main()
{
    FAST_IO;

    FOR(j, 0, 1) build (j);

    cin >> n >> u >> d >> s;

    fairs[MAXN-2].pb({s, 0});

    REP(n) {
        int t;
        ll l, m;
        cin >> t >> l >> m;
        fairs[t].pb({l, m});
    }

    FOR(i, 0, MAXN-1) FOR(j, 0, 1) upd (j, i, -INF);
    FOR(i, 0, MAXN-1) dp[i] = -INF;
    dp[s] = 0;
    ch(s);

    FOR(i, 0, MAXN-1) {
        if ((int)fairs[i].size() == 0) continue;
        sort(fairs[i].begin(), fairs[i].end());

        for (auto p : fairs[i]) {
            ll l = p.f, m = p.s;

            ll cur1 = m - l * d;
            cur1 += getMax(0, 1, l);

            ll cur2 = m + l * u;
            cur2 += getMax(1, l, MAXN-1);

            dp[l] = max(dp[l], cur1);
            dp[l] = max(dp[l], cur2);

        }

        for (auto p : fairs[i]) {
            ll l = p.f;

            ch (l);

          //  cout << " l = " << l << " dp = " << dp[l] << endl;
        }

        for (auto p : fairs[i]) {
            ll l = p.f, m = p.s;

            ll cur = m - l * d;
            cur += getMax(0, 1, l-1);

            upd (0, l, cur + l*d);

            dp[l] = max(dp[l], cur);

          //  cout << " l = " << l << " 0 " << " cur = " << cur << endl;

        }

        reverse(fairs[i].begin(), fairs[i].end());

        for (auto p : fairs[i]) {
            ll l = p.f, m = p.s;

            ll cur = m + l * u;
            cur += getMax(1, l+1, MAXN-1);

            upd (1, l, cur - l*u);

            dp[l] = max(dp[l], cur);

           // cout << " l = " << l << " 1 " << " cur = " << cur << endl;

        }

        //reverse(fairs[i].begin(), fairs[i].end());

        for (auto p : fairs[i]) {
            ll l = p.f;

            ch (l);

          //  cout << " l = " << l << " dp = " << dp[l] << endl;
        }
    }

    cout << dp[s] << "\n";

    return 0;
}


/*
2 1 10 5
1 4 100
1 6 50
*/

• Subtask 1: 100 / 100