Submission #858566

#	Time	Username	Problem	Language	Result	Execution time	Memory
858566		Hanksburger	Salesman (IOI09_salesman)	C++17	100 / 100	252 ms	41044 KiB

salesman

#include <bits/stdc++.h>
using namespace std;
long long L[500005], R[500005], a[500005], b[500005], sum[500005];
vector<pair<long long, long long> > vec[500005];
void updL(long long x, long long y)
{
    for (long long i=x; i<=500001; i+=i&(-i))
        L[i]=max(L[i], y);
}
void updR(long long x, long long y)
{
    for (long long i=x; i<=500001; i+=i&(-i))
        R[i]=max(R[i], y);
}
long long qryL(long long x)
{
    long long res=-1e18;
    for (long long i=x; i; i-=i&(-i))
        res=max(res, L[i]);
    return res;
}
long long qryR(long long x)
{
    long long res=-1e18;
    for (long long i=x; i; i-=i&(-i))
        res=max(res, R[i]);
    return res;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n, u, d, s;
    cin >> n >> u >> d >> s;
    for (long long i=1; i<=n; i++)
    {
        long long x, y, z;
        cin >> x >> y >> z;
        vec[x].push_back({y, z});
    }
    vec[500001].push_back({s, 0});
    for (long long i=1; i<=500001; i++)
        L[i]=R[i]=-1e18;
    updL(s, d*s);
    updR(500002-s, -u*s);
    for (long long i=1; i<=500001; i++)
    {
        long long sz=vec[i].size(), mx=-1e18;
        sort(vec[i].begin(), vec[i].end());
        for (long long j=0; j<sz; j++)
        {
            long long l=vec[i][j].first, m=vec[i][j].second;
            a[j]=max(qryL(l)-d*l+m, qryR(500002-l)+u*l+m);
            sum[j]=(j==0)?m:(sum[j-1]+m);
        }
        for (long long j=0; j<sz; j++)
        {
            long long l=vec[i][j].first;
            mx=max(mx, a[j]+d*l-sum[j]);
            b[j]=mx-d*l+sum[j];
        }
        mx=-1e18;
        for (long long j=sz-1; j>=0; j--)
        {
            long long l=vec[i][j].first;
            mx=max(mx, a[j]-u*l-(sum[sz-1]-(j==0?0:sum[j-1])));
            b[j]=max(b[j], mx+u*l+sum[sz-1]-(j==0?0:sum[j-1]));
        }
        if (i==500001)
        {
            cout << b[0];
            return 0;
        }
        for (long long j=0; j<sz; j++)
        {
            long long l=vec[i][j].first;
            updL(l, b[j]+d*l);
            updR(500002-l, b[j]-u*l);
        }
    }
}

• Subtask 1: 100 / 100