Submission #100787

#	Time	Username	Problem	Language	Result	Execution time	Memory
100787		Alexa2001	Salesman (IOI09_salesman)	C++17	90 / 100	1072 ms	39544 KiB

salesman

#include <bits/stdc++.h>

using namespace std;

const int lim = 5e5 + 2, Nmax = 5e5 + 10, inf = 2e9;

int dp[Nmax], x[Nmax], p[Nmax], come[Nmax];
int n, U, D;

vector<int> event[Nmax];


class AIB
{
    int a[Nmax];
    int ub(int x) { return (x&(-x)); }
public:
    void init()
    {
        int i;
        for(i=0; i<=lim; ++i) a[i] = -inf;
    }

    int query(int pos)
    {
        int ans = -inf;
        for(; pos; pos-=ub(pos)) ans = max(ans, a[pos]);
        return ans;
    }
    void update(int pos, int val)
    {
        for(; pos<=lim; pos+=ub(pos)) a[pos] = max(a[pos], val);
    }
} aib1, aib2;

bool cmp(int a, int b)
{
    return x[a] < x[b];
}

void solve(vector<int> &v)
{
    if(v.empty()) return;

    sort(v.begin(), v.end(), cmp);

    for(auto pos : v)
        come[pos] = max(aib1.query(x[pos]) - D * x[pos], aib2.query(lim - x[pos]) + U * x[pos]);

    int sum = 0, best = -inf;

    for(auto pos : v)
    {
        best = max(best, come[pos] + D * x[pos] - sum);
        sum += p[pos];
        dp[pos] = best + sum - D * x[pos];
    }

    sum = 0; best = -inf;
    reverse(v.begin(), v.end());

    for(auto pos : v)
    {
        best = max(best, come[pos] - U * x[pos] - sum);
        sum += p[pos];
        dp[pos] = max(dp[pos], best + sum + U * x[pos]);
    }

    for(auto pos : v)
    {
        aib1.update(x[pos], dp[pos] + D * x[pos]);
        aib2.update(lim - x[pos], dp[pos] - U * x[pos]);
    }
}

int main()
{
 //   freopen("input", "r", stdin);

    int i, day, S, n;

    cin >> n >> U >> D >> S;

    for(i=1; i<=n; ++i)
    {
        cin >> day >> x[i] >> p[i];
        event[day].push_back(i);
    }

    event[lim+1].push_back(n+1);
    x[n+1] = S; p[n+1] = 0;

    aib1.init(); aib2.init();

    aib1.update(S, D * S);
    aib2.update(lim - S, -U*S);

    for(i=1; i<=lim+1; ++i) solve(event[i]);

    cout << dp[n+1] << '\n';
    return 0;
}

• Subtask 1: 90 / 100