제출 #1022114

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1022114		0npata	Bulldozer (JOI17_bulldozer)	C++17	0 / 100	3 ms	844 KiB

bulldozer

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


#define float double
#define int long long

const float PI = 3.1415;

#define vec vector

struct Point {
	int x;
	int y;
	int w;
	int i;

};

float angle(Point p1, Point p2) {
	Point dif = {p2.x-p1.x, p2.y-p1.y};
	return atan2(dif.y, dif.x);
}


float norm_angle(float angle) {
	while(angle >= 2*PI) angle -= 2*PI;
	return angle;
}

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin >> n;

	vec<Point> ps(n);

	for(int i = 0; i<n; i++) {
		cin >> ps[i].x >> ps[i].y >> ps[i].w;
	}
	sort(ps.begin(), ps.end(), [&](auto p1, auto p2) { return p1.x == p2.x ? p1.y > p2.y : p1.x < p2.x; });
	for(int i = 0; i<n; i++) ps[i].i = i;

	vec<pair<float, pair<int, int>>> evs(0);

	for(int i = 0; i<n; i++) {
		for(int j = i+1; j<n; j++) {
			float cur_angle = angle(ps[i], ps[j]);
			//cerr << "ANGLE: " << cur_angle << '\n';
			float t1 = ((float)3)/2 * PI;
			float t2 = ((float)1)/2 * PI;

			float dif1 = (t1 + 2*PI) - cur_angle;
			float dif2 = (t2 + 2*PI) - cur_angle;


			dif1 = norm_angle(dif1);
			dif2 = norm_angle(dif2);

			// cerr << dif1 << ' ' << dif2 << '\n';

			evs.push_back({dif1, {i, j}});
			evs.push_back({dif2, {i, j}});
		}
	}

	sort(evs.begin(), evs.end());

	vec<int> ap(n);

	iota(ap.begin(), ap.end(), 0);

	int ans = 0;

	for(auto ev: evs) {
		int i = ev.second.first;
		int j = ev.second.second;
		int temp = ps[i].i;
		ps[i].i = ps[j].i;
		ps[j].i = temp;

		//cerr << "swapping: " << i << ' ' << j << " at angle: " << ev.first <<  '\n';

		swap(ap[ps[i].i], ap[ps[j].i]);

		int sum = 0;
		int mx = 0;
		for(int i = 0; i<n; i++) {
			sum += ps[ap[i]].w;
			if(sum < 0) sum = 0;
			mx = max(sum, mx);
		}

		//cerr << mx << '\n';
		ans = max(mx, ans);
	}


	cout << ans << '\n';

}

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