Submission #219543

#	Time	Username	Problem	Language	Result	Execution time	Memory
219543		balbit	Bulldozer (JOI17_bulldozer)	C++14	100 / 100	1036 ms	47912 KiB

bulldozer

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define SZ(x) (int)(x.size())
#define ALL(x) x.begin(),x.end()
#define pb push_back

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<": ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S &&...y) {cerr<<x<<", "; _do(y...);}
#define IOS()

#else
#define IOS() ios::sync_with_stdio(0), cin.tie(0)
#define bug(...)
#define endl '\n'
#endif // BALBIT

//#define assert(...)

const int maxn = 2005;

struct seg{
    ll sum, lv, rv, v;
    seg *lc=0, *rc=0;
};

int n;

void pull(seg *&o) {
    if (!o->lc) {
        if (o->v > 0)
            o->sum = o->lv = o->rv = o->v;
        else {
            o->sum = o->v;
            o->lv = o->rv = o->v = 0;
        }
    }else{
        assert(o->lc && o->rc);
        o->sum = o->lc->sum + o->rc->sum;
        o->lv = max(o->lc->lv, o->lc->sum + o->rc->lv);
        o->rv = max(o->rc->rv, o->rc->sum + o->lc->rv);
        o->v = max({o->lc->v, o->rc->v, o->lc->rv + o->rc->lv});
        assert(o->v >= 0);
    }
}

void MO(int p, ll v, seg *&o, int l=0, int r=n-1) {
    if (l > p || r<p) return;
    if (l == r) {
        o->v = v;
        pull(o);
        return;
    }
    int mid = l+r>>1;
    MO(p,v,o->lc,l,mid);
    MO(p,v,o->rc,mid+1,r);
    pull(o);
}

ll arr[maxn];
void build(seg * &o, int l=0, int r=n-1) {
    if (l == r) {
        o->v = arr[l]; pull(o); return;
    }
    int mid = l+r>>1;
    o->lc = new seg();
    build(o->lc, l, mid);
    o->rc = new seg();
    build(o->rc, mid+1, r);
    pull(o);
}

//#define double long double

struct pt{
    int x, y;
    ll v;
};

struct Ev{
    double sl;
    int a,b;
};

int at[maxn];

signed main(){
    IOS();
    cin>>n;
    seg* root = new seg();
    vector<pt> v(n);

    for (int i = 0; i<n; ++i) {
        cin>>v[i].x>>v[i].y>>v[i].v;
    }

    sort(v.begin(), v.end(), [&](pt a, pt b){return a.y!=b.y?a.y>b.y:a.x<b.x;});

    for (int i = 0; i<n; ++i) {
        arr[i] = v[i].v;
        bug(v[i].v);
        at[i] = i;
    }

    build(root);
    bug(root->v, root->sum);
    bug(root->lv, root->rv);

    ll re = root->v;

    vector<Ev> qu;

    for (int i = 0; i<n; ++i) for (int j = i+1; j<n; ++j) {
        if (v[i].y != v[j].y) {
            qu.pb({-(v[i].x-v[j].x)/(double)(v[i].y-v[j].y), i, j});
        }
    }

    stable_sort(ALL(qu), [&](Ev a, Ev b){return a.sl < b.sl;});

    for (int i = 0; i<SZ(qu); ++i) {
        Ev & e = qu[i];
        bug("swapping", e.a, e.b);
//        assert(abs(at[e.a]-at[e.b]) == 1);
        MO(at[e.a], v[e.b].v, root);
        MO(at[e.b], v[e.a].v, root);
        swap(at[e.a], at[e.b]);
        if (i==SZ(qu)-1 || qu[i+1].sl != qu[i].sl) re = max(re, root->v);
    }

    cout<<re<<endl;

}

Compilation message (stderr)

bulldozer.cpp: In function 'void MO(int, long long int, seg*&, int, int)':
bulldozer.cpp:57:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l+r>>1;
               ~^~
bulldozer.cpp: In function 'void build(seg*&, int, int)':
bulldozer.cpp:68:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l+r>>1;
               ~^~

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