Submission #103924

#	Time	Username	Problem	Language	Result	Execution time	Memory
103924		Bodo171	Bulldozer (JOI17_bulldozer)	C++14	20 / 100	2029 ms	47360 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;
}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 update(int nod,int l,int r,int poz,long long val)
{
    A[poz]=val;
}
void query(int nod,int l,int r,int st,int dr)
{
    long long sum=0;
    for(int i=st;i<=dr;i++)
    {
        sum+=A[i];
        if(sum>ans.mxpref)
            ans.mxpref=1LL*sum;
    }
    sum=0;
    for(int i=dr;i>=st;i--)
    {
        sum+=A[i];
        if(sum>ans.mxsuf)
            ans.mxsuf=1LL*sum;
    }
}
int abss(int x)
{
    if(x<0) return -x;
    return x;
}
int main()
{
    //freopen("data.in","r",stdin);
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>v[i].x>>v[i].y>>v[i].val;
        mx=max(mx,v[i].val);
    }
    sort(v+1,v+n+1,compP);
    for(i=1;i<=n;i++)
    {
        ord[i]=i;
        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=v[i].val+v[j].val;
        ans.mxpref=ans.sum=ans.mxsuf=0;
        if(i>=1)query(1,1,n,1,i-1);
        act+=ans.mxsuf;
        ans.mxpref=ans.sum=ans.mxsuf=0;
        if(j<n) query(1,1,n,j+1,n);
        act+=ans.mxpref;
        if(act>mx)
            mx=1LL*act;
    }
    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;
    }
    sort(pp+1,pp+nr+1,compL);
    for(i=1;i<=nr;i++)
    {
        I=pp[i].i1;J=pp[i].i2;
        swap(ord[I],ord[J]);
      //  if(abss(ord[I]-ord[J])!=1)
     //    cout<<"assert\n";
        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=1LL*v[I].val+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;
    }
    cout<<mx;
    return 0;
}

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