Submission #888639

#	Time	Username	Problem	Language	Result	Execution time	Memory
888639		IBory	Bulldozer (JOI17_bulldozer)	C++17	25 / 100	2024 ms	189564 KiB

bulldozer

#include <bits/stdc++.h>
#define pii pair<ll, ll>
typedef long long ll;
using namespace std;

const int SZ = 1 << 11;
int PN[SZ], IP[SZ];

struct Point {
	ll x, y, s;
	Point(ll x = 0, ll y = 0, ll s = 0) : x(x), y(y), s(s) {};
} P[SZ];

struct Seg {
	struct Data {
		ll LS, RS, T, S;
		Data(ll LS = 0, ll RS = 0, ll T = 0, ll S = 0) : LS(LS), RS(RS), T(T), S(S) {};
		Data operator+(const Data& a) {
			Data ret;
			ret.LS = max(LS, T + a.LS);
			ret.RS = max(a.RS, RS + a.T);
			ret.S = max({S, a.S, RS + a.LS});
			ret.T = T + a.T;
			return ret;
		}
	} T[SZ << 1];

	void Update(int i, int v) {
		T[i += SZ - 1] = Data(max(0, v), max(0, v), v, max(0, v));
		while (i >>= 1) T[i] = T[i * 2] + T[i * 2 + 1];
	}

	ll Query() { return T[1].S; }
} T;

struct Comp {
	bool operator()(const pii& a, const pii& b) const {
		return a.second * b.first > a.first * b.second;
	}
};

void Swap(int a, int b) {
	ll sa = P[a].s, sb = P[b].s;
	swap(IP[PN[a]], IP[PN[b]]);
	swap(PN[a], PN[b]);
	swap(P[a], P[b]);
	T.Update(a, sb);
	T.Update(b, sa);
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N;
	cin >> N;
	for (int i = 1; i <= N; ++i) {
		cin >> P[i].x >> P[i].y >> P[i].s;
		PN[i] = IP[i] = i;
	}
	
	sort(P + 1, P + N + 1, [&](Point a, Point b) {
		if (a.x != b.x) return a.x < b.x;
		return a.y < b.y;
	});
	for (int i = 1; i <= N; ++i) T.Update(i, P[i].s);
	ll ans = T.Query();

	map<pii, vector<pii>, Comp> ord;
	for (int a = 1; a <= N; ++a) for (int b = a + 1; b <= N; ++b) {
		ll xd = P[b].x - P[a].x, yd = P[b].y - P[a].y;
		if (xd < 0) xd *= -1, yd *= -1;
		ll g = gcd(abs(xd), abs(yd)); xd /= g; yd /= g;
		if (xd == 0) yd = 1LL << 31;
		ord[pii{xd, yd}].emplace_back(a, b);
	}

	for (auto& [_, V] : ord) {
		for (auto [a, b] : V) Swap(IP[a], IP[b]);
		ans = max(ans, T.Query());
	}

	cout << ans;
	return 0;
}

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