Submission #224605

#	Time	Username	Problem	Language	Result	Execution time	Memory
224605		dolphingarlic	Bulldozer (JOI17_bulldozer)	C++14	100 / 100	1049 ms	47648 KiB

bulldozer

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

struct X {
	ll l, r, t, b;

	X operator+(X B) {
		return {max(l, t + B.l), max(B.r, r + B.t), t + B.t, max(max(b, B.b), r + B.l)};
	}
} T[8001];

struct Y {
	ll x, y, v;

	bool operator<(Y B) {
		if (x == B.x) return y < B.y;
		return x < B.x;
	}
} P[2001];

struct Z {
	ll x, y;
	int u, v;

	bool operator<(Z B) {
		if (y * B.x == B.y * x) return tie(u, v) < tie(B.u, B.v);
		return y * B.x < B.y * x;
	}
} S[2000001];

int n, curr[2001];

void B(int N = 1, int l = 1, int r = n) {
	if (l == r) {
		ll v = max(P[l].v, 0ll);
		T[N] = {v, v, P[l].v, v};
	} else {
		int M = (l + r) / 2;
		B(N * 2, l, M);
		B(N * 2 + 1, M + 1, r);
		T[N] = T[N * 2] + T[N * 2 + 1];
	}
}

void U(int o, ll a, int N = 1, int l = 1, int r = n) {
	if (l == r) T[N] = {max(a, 0ll), max(a, 0ll), a, max(a, 0ll)};
	else {
		int M = (l + r) / 2;
		if (o > M) U(o, a, N * 2 + 1, M + 1, r);
		else U(o, a, N * 2, l, M);
		T[N] = T[N * 2] + T[N * 2 + 1];
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	FOR(i, 1, n + 1) {
		cin >> P[i].x >> P[i].y >> P[i].v;
		curr[i] = i;
	}
	sort(P + 1, P + n + 1);
	int cnt = 0;
	FOR(i, 1, n + 1) FOR(j, i + 1, n + 1)
		S[cnt++] = {P[j].x - P[i].x, P[j].y - P[i].y, i, j};
	sort(S, S + cnt);

	B();
	ll ans = T[1].b;
	FOR(i, 0, cnt) {
		U(curr[S[i].u], P[S[i].v].v);
		U(curr[S[i].v], P[S[i].u].v);
		swap(curr[S[i].u], curr[S[i].v]);

		if (i == cnt - 1) ans = max(ans, T[1].b);
		else if (S[i].y * S[i + 1].x != S[i + 1].y * S[i].x) ans = max(ans, T[1].b);
	}
	cout << ans;
	return 0;
}

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