Submission #362812

#	Time	Username	Problem	Language	Result	Execution time	Memory
362812		denkendoemeer	Bulldozer (JOI17_bulldozer)	C++14	100 / 100	619 ms	32012 KiB

bulldozer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct pct
{
    int x,y,c;
    bool operator< (const pct &aux) const
    {
        if (x!=aux.x)
            return x<aux.x;
        return y<aux.y;
    }
}w[2005];
struct pct2
{
    int x,y,i,j;
    bool operator< (const pct2 &aux) const
    {
        if (1LL*y*aux.x!=1LL*aux.y*x)
            return 1LL*y*aux.x<1LL*aux.y*x;
        if (i!=aux.i)
            return i<aux.i;
        return j<aux.j;
    }
}v[2000005];
int l[2005];
struct ain
{
    ll l[5000],r[5000],sum[5000],maxi[5000];
    void update(int poz,int val)
    {
        poz+=2048;
        sum[poz]=val;
        l[poz]=r[poz]=maxi[poz]=max(0,val);
        while(poz!=1){
            poz=poz/2;
            sum[poz]=sum[poz*2]+sum[poz*2+1];
            l[poz]=max(l[poz*2],sum[poz*2]+l[poz*2+1]);
            r[poz]=max(r[poz*2+1],sum[poz*2+1]+r[poz*2]);
            maxi[poz]=max(max(maxi[poz*2],maxi[poz*2+1]),r[poz*2]+l[poz*2+1]);
        }
    }
}aint;
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int n,i,j,u=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d%d%d",&w[i].x,&w[i].y,&w[i].c);
    sort(w+1,w+n+1);
    for(i=1;i<n;i++)
        for(j=i+1;j<=n;j++){
            int x=w[j].x-w[i].x,y=w[j].y-w[i].y;
            if (x<0 || (x==0 && y<0))
                x=-x,y=-y;
            v[u++]={x,y,i,j};
        }
    for(i=1;i<=n;i++){
        l[i]=i;
        aint.update(i,w[i].c);
    }
    sort(v,v+u);
    ll ans=aint.maxi[1];
    for(i=0;i<u;i++){
        for(j=i;j<u;j++){
            if (1LL*v[i].x*v[j].y!=1LL*v[i].y*v[j].x)
                break;
            int x=v[j].i,y=v[j].j;
            swap(l[x],l[y]);
            aint.update(l[x],w[x].c);
            aint.update(l[y],w[y].c);
        }
        ans=max(ans,aint.maxi[1]);
        i=j-1;
    }
    printf("%lld\n",ans);
return 0;
}

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   49 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
bulldozer.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |         scanf("%d%d%d",&w[i].x,&w[i].y,&w[i].c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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