Submission #135540

#	Time	Username	Problem	Language	Result	Execution time	Memory
135540		ksmzzang2003	Bulldozer (JOI17_bulldozer)	C++17	0 / 100	2064 ms	604 KiB

bulldozer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
struct sweep
{
    int dx,dy,idx1,idx2;
    int mode()
    {
        return pii(dx,dy)<pii(0,0);
    }
    bool operator <(const sweep &r) const
    {
        ll k = 1ll*dx*r.dy - 1ll*dy*r.dx;
        if(k!=0) return k>0;
        return pii(idx1,idx2) < pii(r.idx1,r.idx2);
    }
};

ll ccw(sweep l,sweep r)
{
    return 1ll*l.dx*r.dy-1ll*r.dx-l.dy;
}

struct point
{
    int x,y,c;
    bool operator <(const point &r)const
    {
        return pii(x,y) < pii(r.x,r.y);
    }
}arr[2005];

struct seg
{
    struct node
    {
        ll sum,lsum,rsum,opt;
    }tree[4010];
    int lim ;
    node make(int x)
    {
        return (node)
        {
            x,max(x,0),max(x,0),max(x,0)
        };
    }
    node merge(node l,node r)
    {
        return (node)
        {
            l.sum+r.sum,max(l.lsum,l.sum+r.lsum),max(r.rsum,r.sum+l.rsum),max({l.opt,r.opt,l.rsum+r.lsum})
        };
    }
    void init(int n,point *arr)
    {
        for(lim=1;lim<=n;lim<<=1);
        for(int j=0;j<n;j++) tree[j+lim] = make(arr[j].c);
        for(int j=lim-1;j;j--) tree[j] = merge(tree[j*2],tree[j*2+1]);
    }
    void update(int x,int v)
    {
        x+=lim; tree[x] = make(v);
        while(x>1)
        {
            x>>=1; tree[x] = merge(tree[2*x],tree[2*x+1]);
        }
    }
    ll query()
    {
        return tree[1].opt;
    }
}seg;
int n,rev[2005]; vector <sweep> v;

int main()
{
    cin>>n; for(int i=0;i<n;i++) cin>>arr[i].x>>arr[i].y>>arr[i].c;
    if(n==1) return !printf("%d",max(0,arr[0].c));
    sort(arr,arr+n);
    iota(rev,rev+n,0);
    for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) v.push_back({arr[j].x-arr[i].x,arr[j].y-arr[i].y,i,j});
    sort(v.begin(),v.end()); seg.init(n,arr);
    ll ans =0;
    for(int i=0;i<v.size();)
    {
        int e = i;
        while(e<v.size() && ccw(v[i],v[e]) ==0) e++;
        for(int j=i;j<e;j++)
        {
            int rx = rev[v[j].idx1],ry=rev[v[j].idx2];
            swap(rev[rx],rev[ry]);
            swap(arr[rx],arr[ry]);
            seg.update(rx,arr[rx].c); seg.update(ry,arr[ry].c);
        }
        ans = max(ans,seg.query());
        i=e;
    }
    cout << ans;
}

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:85:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v.size();)
                 ~^~~~~~~~~
bulldozer.cpp:88:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(e<v.size() && ccw(v[i],v[e]) ==0) e++;
               ~^~~~~~~~~

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