Submission #134313

#	Time	Username	Problem	Language	Result	Execution time	Memory
134313		ksmzzang2003	Bulldozer (JOI17_bulldozer)	C++17	100 / 100	688 ms	33608 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; // cross (dx,dy) (s.dx,s.dy)
        if(k!=0)
            return k>0;
        else if(k==0)
            return pii(idx1,idx2) < pii(r.idx1,r.idx2);
    }
};

ll ccw(sweep a,sweep b)
{
    return 1ll*a.dx*b.dy - 1ll*b.dx*a.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[4100];
    int lim ;
    node make(int x)
    {
        return (node)
        {
            x,max(x,0),max(x,0),max(x,0)
        };
    }
    node merge(node l,node r)
    {
        node ret ;
        ret.sum = l.sum + r.sum;
        ret.lsum = max(l.lsum,l.sum+r.lsum);
        ret.rsum = max(r.rsum,r.sum+l.rsum);
        ret.opt = max({l.opt,r.opt,l.rsum+r.lsum}) ;
        return ret;
    }
    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>=1; 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)
    {
        cout << max(0,arr[0].c);
        return 0;
    }
    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[v[j].idx1],rev[v[j].idx2]);
            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:105:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v.size();)
                 ~^~~~~~~~~
bulldozer.cpp:108:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(e < v.size() && ccw(v[i],v[e]) == 0) e++;
               ~~^~~~~~~~~~
bulldozer.cpp: In member function 'bool sweep::operator<(const sweep&) const':
bulldozer.cpp:20:5: warning: control reaches end of non-void function [-Wreturn-type]
     }
     ^

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