Submission #1210770

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210770		Andrey	Bulldozer (JOI17_bulldozer)	C++20	55 / 100	967 ms	33760 KiB

bulldozer

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

vector<long long> x(5000);
vector<long long> y(5000);
vector<long long> w(5000);

bool comp(pair<long long,long long> a, pair<long long,long long> b) {
    long long x1 = x[a.first]-x[a.second];
    long long y1 = y[a.first]-y[a.second];
    long long x2 = x[b.first]-x[b.second];
    long long y2 = y[b.first]-y[b.second];
    if(x1 < 0) {
        x1*=-1;
        y1*=-1;
    }
    if(x2 < 0) {
        x2*=-1;
        y2*=-1;
    }
    return x1*y2 < x2*y1;
}

bool check(pair<long long,long long> a, pair<long long,long long> b) {
    long long x1 = x[a.first]-x[a.second];
    long long y1 = y[a.first]-y[a.second];
    long long x2 = x[b.first]-x[b.second];
    long long y2 = y[b.first]-y[b.second];
    return x1*y2 == x2*y1;
}

struct node {
    long long pr = 0;
    long long su = 0;
    long long sb = 0;
    long long ans = 0;
};

vector<node> seg(10000);

void upd(long long l, long long r, long long x, long long p, long long c) {
    if(l == r) {
        seg[x].sb = c;
        seg[x].pr = max(c,0LL);
        seg[x].su = max(c,0LL);
        seg[x].ans = max(c,0LL);
        return;
    }
    long long mid = (l+r)/2;
    if(p <= mid) {
        upd(l,mid,x*2,p,c);
    }
    else {
        upd(mid+1,r,x*2+1,p,c);
    }
    seg[x].sb = seg[x*2].sb+seg[x*2+1].sb;
    seg[x].pr = max(seg[x*2].pr,seg[x*2].sb+seg[x*2+1].pr);
    seg[x].su = max(seg[x*2+1].su,seg[x*2+1].sb+seg[x*2].su);
    seg[x].ans = max(seg[x*2].ans,seg[x*2+1].ans);
    seg[x].ans = max(seg[x].ans,seg[x*2].su+seg[x*2+1].pr);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long n;
    cin >> n;
    for(long long i = 0; i < n; i++) {
        cin >> x[i] >> y[i] >> w[i];
    }
    vector<pair<long long,long long>> idk(0);
    for(long long i = 0; i < n; i++) {
        for(long long j = i+1; j < n; j++) {
            if(x[i] != x[j]) {
                idk.push_back({i,j});
            }
        }
    }
    sort(idk.begin(),idk.end(),comp);
    vector<pair<pair<long long,long long>,long long>> apple(0);
    for(long long i = 0; i < n; i++) {
        apple.push_back({{x[i],y[i]},i});
    }
    sort(apple.begin(),apple.end());
    vector<long long> pos(n);
    for(long long i = 0; i < n; i++) {
        upd(0,n-1,1,i,w[apple[i].second]);
        pos[apple[i].second] = i;
    }
    long long ans = 0;
    ans = max(ans,seg[1].ans);
    for(long long i = 0; i < idk.size(); i++) {
        int r = i+1;
        while(r < idk.size() && check(idk[i],idk[r])) {
            r++;
        }
        for(int j = i; j < r; j++) {
            long long a = idk[i].first,b = idk[i].second;
            swap(apple[pos[a]],apple[pos[b]]);
            upd(0,n-1,1,pos[a],w[b]);
            upd(0,n-1,1,pos[b],w[a]);
            swap(pos[a],pos[b]);
            ans = max(ans,seg[1].ans);
        }
        i = r-1;
    }
    cout << ans;
    return 0;
}

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