Submission #197690

# Submission time Handle Problem Language Result Execution time Memory
197690 2020-01-22T10:20:27 Z ksmzzang2003 Bulldozer (JOI17_bulldozer) C++14
0 / 100
6 ms 1532 KB
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld ;
typedef pair <ll,ll> pll ;
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define MAXN 5003
const ll llinf = 0x3f3f3f3f3f3f3f3f;
struct po {
    ll x,y;
    ll co;
    bool operator <(po &r) {
        return pll(x,y) < pll(r.x,r.y);
    }
} arr[MAXN];

struct line {
    ll i,j;
    long double a;
    line(int i,int j,ld a):i(i),j(j),a(a) {}
    bool operator<(line &r) {
        return a>r.a;
    }
};
vector <line>  larr;
ll N;
struct node {
    ll lsum,rsum,sum,ans;
    node() {
        lsum = rsum = sum = ans  =0 ;
    }
    node(ll l,ll r,ll s,ll a) {
        lsum  = l;
        rsum =r;
        sum =s ;
        ans = a;
    }
};
struct seg {
    node tree[5003*4];
    node merge(node l,node r) {
        node ret;
        ret.lsum = max(l.lsum,l.sum + r.lsum);
        ret.rsum = max(r.rsum,l.rsum + r.sum);
        ret.sum  = l.sum + r.sum;
        ret.ans = max({l.ans,r.ans,ret.sum,l.rsum + r.lsum});
        return ret;
    }
    node query(ll nodE,ll ns,ll ne,ll s,ll e) {
        if(e<ns || ne <s )
            return node(0,0,0,0);
        if(s<=ns &&ne <=e)
            return tree[nodE];
        return merge(query(nodE*2,ns,ns + ne >>1,s,e),query(nodE*2+1,(ns+ne>>1) + 1,ne,s,e));
    }
    void update(ll nodE,ll ns,ll ne,ll id,node k) {
        if(ne < id || id < ns)
            return;
        if(ns == ne) {
            tree[nodE] = k;
            return ;
        }
        update(nodE*2,ns,(ns+ne)/2,id,k);
        update(nodE*2+1,(ns+ne)/2+1,ne,id,k);
        tree[nodE] = merge(tree[nodE*2],tree[nodE*2+1]);
    }
} SEG;
int ind[5003];
int main() {
    scanf("%lld",&N);
    for(ll i=1; i<=N; i++)
        scanf("%lld %lld %lld", &arr[i].x,&arr[i].y,&arr[i].co);
    sort(arr+1,arr+1+N);
    for(ll i=1; i<=N; i++) {
        for(ll j=i+1; j<=N; j++) {
            long double deltax = (ld)arr[i].x - arr[j].x;
            long double deltay = (ld)arr[i].y - arr[j].y;
            if(deltax==0)
                deltay = deltax>=0? 1e-18 : -1e-18;
            larr.eb(i,j,deltay/deltax);
        }
    }
    sort(larr.begin(),larr.end());
    for(ll i=1; i<=N; i++) {
        ll C = arr[i].co;
        SEG.update(1,1,N,i,node(C,C,C,C));
    }
    ll res = SEG.query(1,1,N,1,N).ans;
    for(int i=1; i<=N; i++)
        ind[i] =i ;
    for(int i=0; i<larr.size(); i++) {
        int e;
        for(int j=i; j<larr.size(); j++) {
            if(larr[i].a == larr[j].a)
                e = j;
            else
                break;
        }
        for(int j = i ; j<=e; j++) {
            auto it = larr[j];
            ll l = it.i, r = it.j ;
            node x = SEG.query(1,1,N,ind[l],ind[l]);
            node y = SEG.query(1,1,N,ind[r],ind[r]);
            SEG.update(1,1,N,ind[r],x);
            SEG.update(1,1,N,ind[l],y);
            swap(ind[l],ind[r]);
        }
        res = max(res,SEG.query(1,1,N,1,N).ans);
        i=e;
    }
    printf("%lld",res);
}

Compilation message

bulldozer.cpp: In member function 'node seg::query(ll, ll, ll, ll, ll)':
bulldozer.cpp:56:41: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         return merge(query(nodE*2,ns,ns + ne >>1,s,e),query(nodE*2+1,(ns+ne>>1) + 1,ne,s,e));
                                      ~~~^~~~
bulldozer.cpp:56:73: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         return merge(query(nodE*2,ns,ns + ne >>1,s,e),query(nodE*2+1,(ns+ne>>1) + 1,ne,s,e));
                                                                       ~~^~~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:93:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<larr.size(); i++) {
                  ~^~~~~~~~~~~~
bulldozer.cpp:95:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=i; j<larr.size(); j++) {
                      ~^~~~~~~~~~~~
bulldozer.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&N);
     ~~~~~^~~~~~~~~~~
bulldozer.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld %lld", &arr[i].x,&arr[i].y,&arr[i].co);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bulldozer.cpp:94:13: warning: 'e' may be used uninitialized in this function [-Wmaybe-uninitialized]
         int e;
             ^
# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1272 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 6 ms 1528 KB Output is correct
2 Correct 6 ms 1532 KB Output is correct
3 Correct 6 ms 1272 KB Output is correct
4 Correct 6 ms 1400 KB Output is correct
5 Correct 6 ms 1400 KB Output is correct
6 Correct 6 ms 1400 KB Output is correct
7 Correct 6 ms 1420 KB Output is correct
8 Correct 5 ms 1400 KB Output is correct
9 Correct 5 ms 1400 KB Output is correct
10 Correct 5 ms 1300 KB Output is correct
11 Incorrect 3 ms 1016 KB Output isn't correct
12 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 6 ms 1528 KB Output is correct
2 Correct 6 ms 1532 KB Output is correct
3 Correct 6 ms 1272 KB Output is correct
4 Correct 6 ms 1400 KB Output is correct
5 Correct 6 ms 1400 KB Output is correct
6 Correct 6 ms 1400 KB Output is correct
7 Correct 6 ms 1420 KB Output is correct
8 Correct 5 ms 1400 KB Output is correct
9 Correct 5 ms 1400 KB Output is correct
10 Correct 5 ms 1300 KB Output is correct
11 Incorrect 3 ms 1016 KB Output isn't correct
12 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 6 ms 1528 KB Output is correct
2 Correct 6 ms 1532 KB Output is correct
3 Correct 6 ms 1272 KB Output is correct
4 Correct 6 ms 1400 KB Output is correct
5 Correct 6 ms 1400 KB Output is correct
6 Correct 6 ms 1400 KB Output is correct
7 Correct 6 ms 1420 KB Output is correct
8 Correct 5 ms 1400 KB Output is correct
9 Correct 5 ms 1400 KB Output is correct
10 Correct 5 ms 1300 KB Output is correct
11 Incorrect 3 ms 1016 KB Output isn't correct
12 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1272 KB Output isn't correct
2 Halted 0 ms 0 KB -