Submission #545448

#	Time	Username	Problem	Language	Result	Execution time	Memory
545448		alextodoran	Salesman (IOI09_salesman)	C++17	42 / 100	628 ms	51216 KiB

salesman

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 500000;
const int D_MAX = 500000;
const int L_MAX = 500001;

const ll INF = LLONG_MAX / 2;

int N, L, R, S;

struct Fair {
    int day;
    int pos;
    int profit;
};
bool operator < (const Fair &x, const Fair &y) {
    return x.pos < y.pos;
}

Fair fairs[N_MAX + 2];
vector <int> onDay[D_MAX + 2];
vector <int> days;

ll maxStart[N_MAX + 2];
ll maxProfit[N_MAX + 2];

ll maxPref[L_MAX + 2];
ll maxSuff[L_MAX + 2];
void updatePref (int pos, ll val) {
    for (int i = pos; i >= 1; i -= i & -i) {
        maxSuff[i] = max(maxSuff[i], val);
    }
}
void updateSuff (int pos, ll val) {
    for (int i = pos; i <= L_MAX; i += i & -i) {
        maxPref[i] = max(maxPref[i], val);
    }
}
ll queryPref (int pos) {
    ll ret = -INF;
    for (int i = pos; i >= 1; i -= i & -i) {
        ret = max(ret, maxPref[i]);
    }
    return ret;
}
ll querySuff (int pos) {
    ll ret = -INF;
    for (int i = pos; i <= L_MAX; i += i & -i) {
        ret = max(ret, maxSuff[i]);
    }
    return ret;
}

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

    cin >> N >> L >> R >> S;
    for (int i = 1; i <= N; i++) {
        cin >> fairs[i].day >> fairs[i].pos >> fairs[i].profit;
    }

    sort(fairs + 1, fairs + N + 1);
    for (int i = 1; i <= N; i++) {
        onDay[fairs[i].day].push_back(i);
        days.push_back(fairs[i].day);
    }
    sort(days.begin(), days.end());
    days.resize(unique(days.begin(), days.end()) - days.begin());

    fill(maxPref + 1, maxPref + L_MAX + 1, -INF);
    fill(maxSuff + 1, maxSuff + L_MAX + 1, -INF);
    updatePref(S, 0 - (ll) L * S);
    updateSuff(S, 0 + (ll) R * S);
    for (int d : days) {
        for (int i : onDay[d]) {
            maxStart[i] = max(queryPref(fairs[i].pos) - (ll) R * fairs[i].pos,
                              querySuff(fairs[i].pos) + (ll) L * fairs[i].pos);
        }
        ll currMax = -INF;
        for (int x = 0; x < (int) onDay[d].size(); x++) {
            int i = onDay[d][x];
            if (x > 0) {
                int j = onDay[d][x - 1];
                currMax -= (ll) R * (fairs[i].pos - fairs[j].pos);
            }
            currMax = max(currMax, maxStart[i]) + fairs[i].profit;
            maxProfit[i] = currMax;
        }
        currMax = -INF;
        for (int x = (int) onDay[d].size() - 1; x >= 0; x--) {
            int i = onDay[d][x];
            if (x < (int) onDay[d].size() - 1) {
                int j = onDay[d][x + 1];
                currMax -= (ll) L * (fairs[j].pos - fairs[i].pos);
            }
            currMax = max(currMax, maxStart[i]) + fairs[i].profit;
            maxProfit[i] = currMax;
        }
        for (int i : onDay[d]) {
            updatePref(fairs[i].pos, maxProfit[i] - (ll) L * fairs[i].pos);
            updateSuff(fairs[i].pos, maxProfit[i] + (ll) R * fairs[i].pos);
        }
    }

    ll answer = -INF;
    for (int i = 1; i <= N; i++) {
        if (fairs[i].pos < S) {
            maxProfit[i] -= (ll) (S - fairs[i].pos) * R;
        } else {
            maxProfit[i] -= (ll) (fairs[i].pos - S) * L;
        }
        answer = max(answer, maxProfit[i]);
    }
    cout << answer << "\n";

    return 0;
}

• Subtask 1: 42 / 100