Submission #843636

#	Time	Username	Problem	Language	Result	Execution time	Memory
843636		Cookie	Bulldozer (JOI17_bulldozer)	C++14	100 / 100	789 ms	68296 KiB

bulldozer

#include<bits/stdc++.h>
#include<fstream>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>

const int mxn = 2005;
const ll inf = 1e18, mod = 1e9 + 7;
struct P{
    int x, y; ll w;
    bool operator <(const P &b){
        if(x != b.x)return(x < b.x);
        return(y < b.y);
    }
};
struct E{
    ll x, y, u, v;
    bool operator <(const E &b){
        ll val1 = y * b.x, val2 = b.y * x;
        if(val1 != val2)return(val1 < val2);
        return(make_pair(u, v) < make_pair(b.u, b.v));
    }
};
struct Node{
    ll sm, b, p, s;
};
Node comb(Node a, Node b){
    Node res; 
    res.sm = a.sm + b.sm;
    res.p = max(a.p, a.sm + b.p);
    res.s = max(b.s, b.sm + a.s);
    res.b = max(max(a.b, b.b), a.s + b.p);
    return(res);
}
Node st[(mxn << 2) | 1];
void upd(int nd, int l, int r, int id, ll v){
    if(l > id || r < id)return;
    if(l == r){
        st[nd].p = st[nd].s = st[nd].b = st[nd].sm = v;
        return;
    }
    int mid = (l + r) >> 1;
    upd(nd << 1, l, mid, id, v); upd(nd << 1 | 1, mid + 1, r, id, v);
    st[nd] = comb(st[nd << 1], st[nd << 1 | 1]);
}
Node get(int nd, int l, int r, int ql, int qr){
    if(ql <= l && qr >= r)return(st[nd]);
    int mid = (l + r) >> 1;
    if(ql > mid)return(get(nd << 1 | 1, mid + 1, r, ql, qr));
    else if(qr <= mid)return(get(nd << 1, l, mid, ql, qr));
    return(comb(get(nd << 1, l, mid, ql, qr), get(nd << 1 | 1, mid + 1, r, ql, qr)));
}
int n;
P a[mxn + 1];
vt<E>edge;
int pos[mxn + 1];
signed main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i].x >> a[i].y >> a[i].w; 
    }
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; i++){
        pos[i] = i;
        for(int j = i + 1; j <= n; j++){
            edge.pb({a[j].x - a[i].x, a[j].y - a[i].y, i, j});
        }
    }
    sort(edge.begin(), edge.end());
    for(int i = 1; i <= n; i++){
        upd(1, 1, n, i, a[i].w);
    }
    ll ans = max((ll)0, st[1].b);
    for(int i = 0; i < sz(edge);){
        int r = i;
        while(r < sz(edge) && edge[i].y * edge[r].x == edge[r].y * edge[i].x)r++;
        for(int j = i; j < r; j++){
            int u = edge[j].u, v = edge[j].v;
            swap(pos[u], pos[v]);
            upd(1, 1, n, pos[u], a[u].w); upd(1, 1, n, pos[v], a[v].w);
        }
        ans = max(ans, st[1].b);
        i = r;
    }
    cout << ans;
    return(0);
}

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