Submission #869104

#	Time	Username	Problem	Language	Result	Execution time	Memory
869104		HuyQuang_re_Zero	Salesman (IOI09_salesman)	C++14	100 / 100	394 ms	38952 KiB

salesman

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#define N 500005
using namespace std;
struct pt { int day,pos,earn; } a[N];
ll n,L,R,Home,Begin[N],f[N],res,m,i,j,pos;
const ll oo=round(1e18);
struct Fenwick_Tree
{
    ll d[N],bit[N];
    void Init()
    {
        for(int i=1;i<=m;i++) d[i]=bit[i]=-oo;
    }
    void update(int i,ll k)
    {
        d[i]=max(d[i],k);
        while(i<=m) bit[i]=max(bit[i],k),i+=(i & -i);
    }
    ll get(int l,int r)
    {
        ll res=-oo,i=r;
        while(i>=l)
            if(i-(i & -i)>=l) res=max(res,bit[i]),i-=(i & -i);
            else res=max(res,d[i]),i--;
        return res;
    }
} FTL,FTR;
void consider(int u,ll k)
{
    FTL.update(u,k+R*u);
    FTR.update(u,k-L*u);
}
int main()
{
  //  freopen("salesman.inp","r",stdin);
    //freopen("salesman.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>L>>R>>Home;
    for(i=1;i<=n;i++) cin>>a[i].day>>a[i].pos>>a[i].earn;
    sort(a+1,a+n+1,[&](pt a,pt b){ return a.day<b.day || (a.day==b.day && a.pos<b.pos); });
    m=500001;
    FTL.Init();
    FTR.Init();
    consider(Home,0);
    pos=1;
    for(i=1;i<=n;i++)
        if(i==n || a[i].day<a[i+1].day)
        {
            for(j=pos;j<=i;j++)
                Begin[j]=max(FTL.get(1,a[j].pos)+a[j].earn-R*a[j].pos,
                             FTR.get(a[j].pos,m)+a[j].earn+L*a[j].pos);

            ll ma=-oo,sum=0;
            for(j=pos;j<=i;j++)
            {
                sum+=a[j].earn;
                ma=max(ma,Begin[j]-sum+R*a[j].pos);
                f[j]=sum+ma-R*a[j].pos;
            }

            ma=-oo,sum=0;
            for(j=i;j>=pos;j--)
            {
                sum+=a[j].earn;
                ma=max(ma,Begin[j]-sum-L*a[j].pos);
                f[j]=max(f[j],sum+ma+L*a[j].pos);
            }

            for(j=pos;j<=i;j++)
            {
                consider(a[j].pos,f[j]);
                if(a[j].pos>=Home) res=max(res,f[j]-L*(a[j].pos-Home));
                else res=max(res,f[j]-R*(Home-a[j].pos));
            }
            pos=i+1;
        }
    cout<<res;
}

• Subtask 1: 100 / 100