Submission #1022143

#	Time	Username	Problem	Language	Result	Execution time	Memory
1022143		0npata	Bulldozer (JOI17_bulldozer)	C++17	25 / 100	2070 ms	100252 KiB

bulldozer

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


#define float double
#define int long long

const float PI = 3.14159265358979323846;
const float EPSILON = 0.0000000001;

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

	auto eval = [&]() {
		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);
	};

	evs.push_back({1'000, {}});

	eval();
	for(int ei = 0; ei < evs.size()-1; ei++) {
		auto ev = evs[ei];

	        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(abs(evs[ei+1].first - evs[ei].first) < EPSILON) continue;

		eval();
	}
	//eval();


	cout << ans << '\n';

}

Compilation message (stderr)

bulldozer.cpp: In function 'int32_t main()':
bulldozer.cpp:94:21: 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]
   94 |  for(int ei = 0; ei < evs.size()-1; ei++) {
      |                  ~~~^~~~~~~~~~~~~~

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