oj.uz

Submission #136538

# Submission time Handle Problem Language Result Execution time Memory
136538 2019-07-25T12:46:31 Z ksmzzang2003 Bulldozer (JOI17_bulldozer) C++17
0 / 100
 3 ms 504 KB 
#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>=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[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

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -