제출 #32622

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
32622		aome	Bulldozer (JOI17_bulldozer)	C++14	80 / 100	930 ms	64020 KiB

bulldozer

#include <bits/stdc++.h>
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; }
};
 
struct Go {
	double w;
	int x, y;
 
	Go (double w, int x, int y) :
		w(w), x(x), y(y) {}
};
 
int n, pos[N];
long long res;
Node it[4 * N];
vector<Go> 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]);
}
 
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) {
			double tmp = atan2(a[j].y - a[i].y, a[j].x - a[i].x);
			if (tmp == acos(-1)) tmp = 0;
			go.push_back(Go(tmp, i, j));
		}
	}
	sort(go.begin(), go.end(), [&](Go x, Go y) {
		return make_pair(x.w, make_pair(x.x, x.y)) < make_pair(y.w, make_pair(y.x, y.y));
	});
	for (int i = 0; i < go.size(); ++i) {
		vector<Go> _go;
		_go.push_back(go[i]);
		while (i + 1 < go.size() && go[i + 1].w == go[i].w) {
			i++, _go.push_back(go[i]);
		}
		for (auto j : _go) {
			// cout << j.x << ' ' << j.y << '\n';
			swap(pos[j.x], pos[j.y]);
			upd(1, 0, n - 1, pos[j.x], a[j.x].w);
			upd(1, 0, n - 1, pos[j.y], a[j.y].w);
		}
		// for (int j = 0; j < n; ++j) cout << pos[j] << ' '; cout << '\n';
		res = max(res, it[1].mx);
	}
	cout << res << '\n';
}

컴파일 시 표준 에러 (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() && go[i + 1].w == go[i].w) {
          ~~~~~~^~~~~~~~~~~

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