Submission #947934

#	Time	Username	Problem	Language	Result	Execution time	Memory
947934		ha819ha	Bulldozer (JOI17_bulldozer)	C++17	100 / 100	558 ms	33568 KiB

bulldozer

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

using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

#define x first
#define y second
#define all(v) (v).begin(), (v).end()

const int SZ = 2048;
struct Tree {
	long long L[SZ + SZ], R[SZ + SZ], S[SZ + SZ], M[SZ + SZ];
	void Put(int a, int b) {
		a += SZ;
		S[a] = b;
		L[a] = R[a] = M[a] = max(0, b);
		while (a != 1) {
			a >>= 1;
			S[a] = S[a + a] + S[a + a + 1];
			L[a] = max(L[a + a], S[a + a] + L[a + a + 1]);
			R[a] = max(R[a + a + 1], S[a + a + 1] + R[a + a]);
			M[a] = max(max(M[a + a], M[a + a + 1]), R[a + a] + L[a + a + 1]);
		}
	}
}T;

struct Point {
    int x,y,v;

    bool operator < (const Point& rhs) const {
        return pii(x, y) < pii(rhs.x, rhs.y);
    }
};

struct Line {
	int x, y, i, j;
	bool operator<(const Line &p)const {
		return (long long)y*p.x  != (long long)p.y*x ? (long long)y*p.x < (long long)p.y*x : i!=p.i?i<p.i:j<p.j;
	}
};

int main(void){
    cin.tie(0)->sync_with_stdio(0);

    int n; cin>>n;
    vector<Point> p(n);
    for(auto& [x,y,v]:p) cin>>x>>y>>v;

    sort(all(p));
    vector<int> pos(n);

    vector<Line> lines;

    for(int i=0;i<n;i++) {
        for(int j=i+1;j<n;j++) {
            int dx = p[j].x-p[i].x;
            int dy = p[j].y-p[i].y;
            if (dx < 0 || (dx == 0 && dy < 0))dx = -dx, dy = -dy;
            lines.push_back({dx,dy,i,j});
        }
    }
    sort(all(lines));

    for(int i=0;i<n;i++) {
        T.Put(i, p[i].v);
        pos[i]=i;
    }

    ll ans = T.M[1];

    int cnt = lines.size();
	for (int i = 0,j; i < cnt; i++) {
		for (j = i; j < cnt; j++) {
            if ((long long)lines[i].x*lines[j].y != (long long)lines[i].y*lines[j].x)break;
            int a = lines[j].i, b = lines[j].j;
            swap(pos[a], pos[b]);

            T.Put(pos[a], p[a].v);
            T.Put(pos[b], p[b].v);
        }
        ans = max(ans, T.M[1]);
        i=j-1;
    }
    cout<<ans;
}

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