제출 #270362

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
270362		MKopchev	Bulldozer (JOI17_bulldozer)	C++14	25 / 100	2086 ms	121340 KiB

bulldozer

#include<bits/stdc++.h>
using namespace std;

const int nmax=2e3+42;

struct info
{
    long long x,y,gain;
};

int n;

info inp[nmax];

bool cmp(pair<long long,long long> a,pair<long long,long long> b)
{
    return a.first*b.second<a.second*b.first;
}

pair<long long,long long> cur;

bool eq(info u,info v)
{
    return (u.x-v.x)*cur.second==cur.first*(u.y-v.y);
}


bool cmp_2(info u,info v)
{
    return (u.x-v.x)*cur.second<cur.first*(u.y-v.y);
}
long long solve(pair<long long,long long> a)
{
    cur=a;

    sort(inp+1,inp+n+1,cmp_2);

    long long ret=0,cur_best=0,sum_now=0;

    for(int i=1;i<=n;i++)
    {
        sum_now+=inp[i].gain;

        if(eq(inp[i],inp[i+1])==0||i==n)
        {
            cur_best=max(cur_best+sum_now,sum_now);
            sum_now=0;
        }

        ret=max(ret,cur_best);
    }
    return ret;
}

struct line
{
    int i,j;
    long long up;
    long long down;
};

vector<line> all,help;

bool eq_line(line u,line v)
{
    return u.up*v.down==u.down*v.up;
}

bool cmp_line(line a,line b)
{
    if(a.up*b.down!=a.down*b.up)return a.up*b.down<a.down*b.up;
    if(a.j!=b.j)return a.j>b.j;
    return a.i>b.i;
}

struct mem
{
    long long sum,mx_pref,mx_suff,mx_interval;
};

mem tree[4*nmax];

mem my_merge(mem a,mem b)
{
    mem ret;
    ret.sum=a.sum+b.sum;
    ret.mx_pref=max(a.mx_pref,a.sum+b.mx_pref);
    ret.mx_suff=max(b.mx_suff,b.sum+a.mx_suff);

    ret.mx_interval=max(a.mx_interval,b.mx_interval);
    ret.mx_interval=max(ret.mx_interval,a.mx_suff+b.mx_pref);
    return ret;
}
void update(int node,int l,int r,int pos,long long add)
{
    if(l==r)
    {
        tree[node].sum+=add;
        tree[node].mx_pref=max(tree[node].sum,0LL);
        tree[node].mx_suff=max(tree[node].sum,0LL);
        tree[node].mx_interval=max(tree[node].sum,0LL);
        return;
    }

    int av=(l+r)/2;

    if(pos<=av)update(node*2,l,av,pos,add);
    else update(node*2+1,av+1,r,pos,add);

    tree[node]=my_merge(tree[node*2],tree[node*2+1]);
}

int where[nmax];

int main()
{
    scanf("%i",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld%lld",&inp[i].x,&inp[i].y,&inp[i].gain);

    if(n==1)
    {
        printf("%lld\n",max(0LL,inp[1].gain));
        return 0;
    }

    pair<long long,long long> start={0,1};

    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        {
            long long up=inp[i].x-inp[j].x;
            long long down=inp[i].y-inp[j].y;

            if(down)
            {
                if(down<0)down=-down,up=-up;

                if(up*start.second<down*start.first)start={up,down};
            }
        }
    start.first--;

    long long outp=0;

    outp=max(outp,solve(start));

    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
        {
            line cur;
            cur.i=i;
            cur.j=j;

            long long up=inp[i].x-inp[j].x;
            long long down=inp[i].y-inp[j].y;

            if(down)
            {
                if(down<0)down=-down,up=-up;

                cur.up=up;
                cur.down=down;

                all.push_back(cur);
            }
        }

    if(all.size())
    {
    sort(all.begin(),all.end(),cmp_line);

    help.push_back(all[0]);

    for(auto k:all)
        if(k.i!=help.back().i||k.j!=help.back().j)help.push_back(k);

    all=help;
    }

    for(int i=1;i<=n;i++)
    {
        where[i]=i;
        update(1,1,n,i,inp[i].gain);
    }

    for(int i=0;i<all.size();i++)
    {
        int j=i;

        for(j=i;j<all.size()&&eq_line(all[i],all[j]);j++)
        {
        int le=where[all[j].i];
        int ri=where[all[j].j];
        /*
        cout<<all[j].i<<" "<<all[j].j<<" -> "<<le<<" "<<ri<<" "<<all[j].up<<" "<<all[j].down<<endl;
        for(int t=1;t<=n;t++)cout<<where[t]<<" ";cout<<endl;
        */
        assert(abs(le-ri)==1);

        update(1,1,n,le,-inp[le].gain);
        update(1,1,n,ri,-inp[ri].gain);

        swap(where[all[j].i],where[all[j].j]);
        swap(inp[le],inp[ri]);

        update(1,1,n,le,+inp[le].gain);
        update(1,1,n,ri,+inp[ri].gain);
        }

        i=j-1;

        outp=max(outp,tree[1].mx_interval);
    }

    printf("%lld\n",outp);
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:187:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  187 |     for(int i=0;i<all.size();i++)
      |                 ~^~~~~~~~~~~
bulldozer.cpp:191:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |         for(j=i;j<all.size()&&eq_line(all[i],all[j]);j++)
      |                 ~^~~~~~~~~~~
bulldozer.cpp:117:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  117 |     scanf("%i",&n);
      |     ~~~~~^~~~~~~~~
bulldozer.cpp:119:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  119 |         scanf("%lld%lld%lld",&inp[i].x,&inp[i].y,&inp[i].gain);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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