oj.uz

Submission #135540

# Submission time Handle Problem Language Result Execution time Memory
135540 2019-07-24T07:53:31 Z ksmzzang2003 Bulldozer (JOI17_bulldozer) C++17
0 / 100
 2000 ms 604 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2047 ms 504 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2064 ms 604 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2064 ms 604 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2064 ms 604 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2047 ms 504 KB Time limit exceeded
2 Halted 0 ms 0 KB -