Submission #103950

#	Time	Username	Problem	Language	Result	Execution time	Memory
103950		Bodo171	Bulldozer (JOI17_bulldozer)	C++14	25 / 100	2028 ms	47352 KiB

bulldozer

#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
const int nmax=2005;
struct point
{
    long long x,y,val;
}v[nmax];
struct line
{
    long long nr,nm;
    int i1,i2;
}pp[nmax*nmax/2];
struct node
{
    long long mxsuf,mxpref,sum;
}arb[4*nmax],ans;
pair<long long,long long> lin=make_pair(-2*1000*1000*1000-1,1);
bool compP(point unu,point doi)
{
    return (1LL*unu.x*lin.first+1LL*unu.y*lin.second<1LL*doi.x*lin.first+1LL*doi.y*lin.second);
}
bool compL(line unu,line doi)
{
    return (1LL*unu.nr*doi.nm<1LL*unu.nm*doi.nr);
}
int ord[nmax];
long long A[nmax];
int n,i,j,nr,I,J,poz;
long long act,mx;
void mrg(node &A,node B,node C)
{
    A.sum=1LL*B.sum+C.sum;
    A.mxpref=max(B.mxpref,B.sum+C.mxpref);
    A.mxsuf=max(C.mxsuf,C.sum+B.mxsuf);
}
void update(int nod,int l,int r,int poz,long long val)
{
    if(l==r)
    {
        arb[nod].mxpref=arb[nod].mxsuf=max(val,0LL);
        arb[nod].sum=val;
        return;
    }
    int m=(l+r)/2;
    if(poz<=m) update(2*nod,l,m,poz,val);
    else update(2*nod+1,m+1,r,poz,val);
    mrg(arb[nod],arb[2*nod],arb[2*nod+1]);
}
void query(int nod,int l,int r,int st,int dr)
{
    if(st<=l&&r<=dr)
    {
        mrg(ans,ans,arb[nod]);
        return;
    }
    int m=(l+r)/2;
    if(st<=m) query(2*nod,l,m,st,dr);
    if(m<dr) query(2*nod+1,m+1,r,st,dr);
}
int abss(int x)
{
    if(x<0) return -x;
    return x;
}
void slv()
{
    for(int i=1;i<=n;i++)
    {
        act=0;
        for(int j=i;j<=n;j++)
        {
            act+=v[j].val;
            if(act>mx)
                mx=act;
        }
    }
}
int main()
{
    //freopen("data.in","r",stdin);
    cin>>n;
    bool solve0=1;
    for(i=1;i<=n;i++)
    {
        cin>>v[i].x>>v[i].y>>v[i].val;
        mx=max(mx,v[i].val);
        if(v[i].y!=0)
            solve0=0;
    }
    sort(v+1,v+n+1,compP);
    if(solve0)
    {
        slv();
        cout<<mx;
        return 0;
    }
    for(i=1;i<=n;i++)
    {
        ord[i]=i;
        if(v[i-1].x==v[i].x&&i>1)update(1,1,n,i-1,v[i].val);
        else update(1,1,n,i,v[i].val);
    }
    for(i=1;i<=n;i++)
        for(j=i+1;j<=n;j++)
            if(v[i].x==v[j].x)
    {
        act=0;
        update(1,1,n,i,v[i].val);
        update(1,1,n,j,v[j].val);
        ans.mxpref=ans.sum=ans.mxsuf=0;
        if(i>=1)query(1,1,n,1,i);
        act+=ans.mxsuf;
        ans.mxpref=ans.sum=ans.mxsuf=0;
        if(j<=n) query(1,1,n,j,n);
        act+=ans.mxpref;
        if(act>mx)
            mx=1LL*act;
        update(1,1,n,i,v[i].val+v[j].val);
        update(1,1,n,j,0);
    }
    else
    {
        pp[++nr]={v[j].y-v[i].y,v[j].x-v[i].x,i,j};
        if(pp[nr].nm<0)
            pp[nr].nr*=-1,pp[nr].nm*=-1;
    }
    for(i=1;i<=n;i++)
        update(1,1,n,i,v[i].val);
    sort(pp+1,pp+nr+1,compL);
    int lim;
    for(i=1;i<=nr;i++)
    {
        for(j=i;j<=nr&&1LL*pp[i].nm*pp[j].nr==1LL*pp[i].nr*pp[j].nm;j++);
        j--;
        lim=j;
        for(j=i;j<=lim;j++)
        {
           I=pp[j].i1;
           J=pp[j].i2;
           update(1,1,n,ord[I],v[I].val+v[J].val);
           update(1,1,n,ord[J],0);
        }
        for(j=i;j<=lim;j++)
        {
            I=pp[j].i1;
            J=pp[j].i2;
            swap(ord[I],ord[J]);
            poz=min(ord[I],ord[J]);
            update(1,1,n,ord[I],v[I].val);
            update(1,1,n,ord[J],v[J].val);
            act=0;
            ans.mxpref=ans.sum=ans.mxsuf=0;
            if(poz>=1)query(1,1,n,1,poz);
            act+=ans.mxsuf;
            ans.mxpref=ans.sum=ans.mxsuf=0;
            if(poz+1<=n)query(1,1,n,poz+1,n);
            act+=ans.mxpref;
            if(act>mx)
                mx=1LL*act;
           update(1,1,n,ord[I],v[I].val+v[J].val);
           update(1,1,n,ord[J],0);
        }
        for(j=i;j<=lim;j++)
        {
           I=pp[j].i1;
           J=pp[j].i2;
           update(1,1,n,ord[I],v[I].val);
           update(1,1,n,ord[J],v[J].val);
        }
        i=lim;
    }
    cout<<mx;
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 20 / 20
• Subtask 3: 0 / 35
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20