Submission #32623

#	Time	Username	Problem	Language	Result	Execution time	Memory
32623		aome	Bulldozer (JOI17_bulldozer)	C++14	100 / 100	996 ms	32352 KiB

bulldozer

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
 
const int N = 2005;
const int INF = 1e9;
 
struct Point {
	int x, y, w;
} a[N];
 
struct Node {
	long long s, sl, sr, mx;
 
	Node () { s = sl = sr = 0, mx = -INF; }
};

typedef pair<int, int> ii;
 
int n, pos[N];
long long res;
Node it[4 * N];
vector<ii> go;
 
Node Merge(Node x, Node y) {
	Node z;
	z.s = x.s + y.s;
	z.sl = max(x.sl, x.s + y.sl);
	z.sr = max(x.sr + y.s, y.sr);
	z.mx = max(max(x.mx, y.mx), x.sr + y.sl);
	return z;
}
 
void build(int i, int l, int r) {
	if (l == r) {
		it[i].s = it[i].sl = it[i].sr = it[i].mx = a[l].w; return;
	}
	int mid = (l + r) >> 1;
	build(i << 1, l, mid), build(i << 1 | 1, mid + 1, r);
	it[i] = Merge(it[i << 1], it[i << 1 | 1]);
}
 
void upd(int i, int l, int r, int p, int v) {
	if (l == r) {
		it[i].s = it[i].sl = it[i].sr = it[i].mx = v; return;
	}
	int mid = (l + r) >> 1;
	if (p <= mid) upd(i << 1, l, mid, p, v);
	else upd(i << 1 | 1, mid + 1, r, p, v);
	it[i] = Merge(it[i << 1], it[i << 1 | 1]);
}

long long cal(ii x, ii y) {
	return 1LL * (a[x.fi].y - a[x.se].y) * (a[y.fi].x - a[y.se].x) - 1LL * (a[y.fi].y - a[y.se].y) * (a[x.fi].x - a[x.se].x);
}
 
int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> a[i].x >> a[i].y >> a[i].w;
	}
	sort(a, a + n, [&](Point x, Point y) {
		return make_pair(x.y, x.x) < make_pair(y.y, y.x);
	});
	// for (int i = 0; i < n; ++i) {
	// 	cout << a[i].x << ' ' << a[i].y << ' ' << a[i].w << '\n';
	// }
	for (int i = 0; i < n; ++i) pos[i] = i;
	build(1, 0, n - 1);
	res = max(res, it[1].mx);
	for (int  i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			go.push_back(ii(i, j));
		}
	}
	sort(go.begin(), go.end(), [&](ii x, ii y) {
		long long tmp = cal(x, y);
		return tmp == 0 ? x < y : tmp < 0;
	});
	// for (auto i : go) cout << i.fi << ' ' << i.se << '\n';
	for (int i = 0; i < go.size(); ++i) {
		vector<ii> _go;
		_go.push_back(go[i]);
		while (i + 1 < go.size() && !cal(go[i], go[i + 1])) {
			i++, _go.push_back(go[i]);
		}
		for (auto j : _go) {
			// cout << j.x << ' ' << j.y << '\n';
			swap(pos[j.fi], pos[j.se]);
			upd(1, 0, n - 1, pos[j.fi], a[j.fi].w);
			upd(1, 0, n - 1, pos[j.se], a[j.se].w);
		}
		// for (int j = 0; j < n; ++j) cout << pos[j] << ' '; cout << '\n';
		res = max(res, it[1].mx);
	}
	cout << res << '\n';
}

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:83:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < go.size(); ++i) {
                  ~~^~~~~~~~~~~
bulldozer.cpp:86:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (i + 1 < go.size() && !cal(go[i], go[i + 1])) {
          ~~~~~~^~~~~~~~~~~

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