Submission #1022106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022106		0npata	Bulldozer (JOI17_bulldozer)	C++17	0 / 100	2 ms	796 KiB

bulldozer

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


#define float double
#define int long long

const float PI = 3.14159;
const float EPSILON = 0.0001;

#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 + EPSILON) - cur_angle;
			float dif2 = (t2 + 2*PI + EPSILON) - cur_angle;

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

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

	vec<int> ap(n);

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

	int ans = 0;

	evs.push_back({1000000000000000, {}});

	for(int l = 0; l<evs.size()-1; l++) {
		auto ev = evs[l];
		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]);

		if(evs[l].first - evs[l+1].first < EPSILON) continue;

		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';

}

Compilation message (stderr)

bulldozer.cpp: In function 'int32_t main()':
bulldozer.cpp:75:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<double, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |  for(int l = 0; l<evs.size()-1; l++) {
      |                 ~^~~~~~~~~~~~~

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