Submission #136537

#	Time	Username	Problem	Language	Result	Execution time	Memory
136537		ksmzzang2003	Bulldozer (JOI17_bulldozer)	C++17	0 / 100	3 ms	632 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;
    bool operator <(const sweep &r) const{
        ll k = 1ll*dx*r.dy - 1ll*dy*r.dx;
        return (k!=0)?(k>0) : (pii(idx1,idx2) < pii(r.idx1,r.idx2));
    }
};

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

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,rsum,lsum,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>=0;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[x*2],tree[x*2+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[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:68:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<v.size();){
                 ~^~~~~~~~~
bulldozer.cpp:70: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