Submission #51518

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
51518	2018-06-18T05:10:16 Z	spencercompton	Bulldozer (JOI17_bulldozer)	C++17	5 / 100	31 ms	396 KB

bulldozer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
double ptLineDist(double x1, double y1, double x2, double y2, double px, double py){
	double pd2 = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
	double x, y;
	if(pd2 == 0){
		x = x1;
		y = y2;
	}
	else{
		double u = ((px-x1) * (x2 - x1) + (py - y1) * (y2-y1)) / pd2;
		x = x1 + u * (x2 - x1);
		y = y1 + u * (y2 - y1);
	}
	return (x-px) * (x - px) + (y - py) * (y - py);
}

int main(){
	int n;
	cin >> n;
	ll ans = 0LL;
	ll x[n];
	ll y[n];
	ll v[n];
	for(int i = 0; i<n; i++){
		cin >> x[i] >> y[i] >> v[i];
	}
	for(int i = 0; i<n; i++){
		ans = max(ans,v[i]);
		for(int j = i+1; j<n; j++){
			ll dx = x[j]-x[i];
			ll dy = y[j]-y[i];
			//(dy,-dx);
			vector<pair<double, ll> > li;
			for(int k = 0; k<n; k++){
				bool cross = (y[k]+dx)*(dy-0LL) > (-dx-0LL)*(x[k]-dy);
				double dist = ptLineDist(0LL, 0LL, dy, -dx, x[k], y[k]);
				if(cross){
					li.push_back(make_pair(dist,v[k]));
				}
				else{
					li.push_back(make_pair(-dist,v[k]));
				}
			}
			sort(li.begin(),li.end());
			ll bestPre = 0LL;
			ll cur = 0LL;
			double tol = -1;
			for(int k = 0; k<n; k++){
				if(k>0 && li[k].first-li[k-1].first>tol){
					bestPre = min(bestPre,cur);
				}
				cur += li[k].second;
				if(k==n-1 || li[k+1].first-li[k].first>tol){
					ans = max(ans,cur-bestPre);
				}
			}
		}
	}

	// for(int i = 0; i<n; i++){
	// 	ans = max(ans,v[i]);
	// 	for(int j = i+1; j<n; j++){
	// 		ans = max(ans,v[i]+v[j]);
	// 		ll dx = x[j]-x[i];
	// 		ll dy = y[j]-y[i];
	// 		swap(dx,dy);
	// 		dx = -dx;
	// 		//(dy,-dx);
	// 		vector<pair<double, ll> > li;
	// 		for(int k = 0; k<n; k++){
	// 			bool cross = (y[k]+dx)*(dy-0LL) > (-dx-0LL)*(x[k]-dy);
	// 			double dist = ptLineDist(0LL, 0LL, dy, -dx, x[k], y[k]);
	// 			if(cross){
	// 				li.push_back(make_pair(dist,v[k]));
	// 			}
	// 			else{
	// 				li.push_back(make_pair(-dist,v[k]));
	// 			}
	// 		}
	// 		sort(li.begin(),li.end());
	// 		ll bestPre = 0LL;
	// 		ll cur = 0LL;
	// 		double tol = -1;
	// 		for(int k = 0; k<n; k++){
	// 			if(k>0 && li[k].first-li[k-1].first>tol){
	// 				bestPre = min(bestPre,cur);
	// 			}
	// 			cur += li[k].second;
	// 			if(k==n-1 || li[k+1].first-li[k].first>tol){
	// 				ans = max(ans,cur-bestPre);
	// 			}
	// 		}
	// 	}
	// }
	cout << ans << endl;
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	256 KB	Output is correct
2	Correct	17 ms	376 KB	Output is correct
3	Correct	18 ms	256 KB	Output is correct
4	Correct	18 ms	384 KB	Output is correct
5	Correct	18 ms	256 KB	Output is correct
6	Correct	17 ms	256 KB	Output is correct
7	Correct	18 ms	384 KB	Output is correct
8	Correct	18 ms	256 KB	Output is correct
9	Correct	17 ms	256 KB	Output is correct
10	Correct	17 ms	256 KB	Output is correct
11	Correct	2 ms	256 KB	Output is correct
12	Correct	2 ms	256 KB	Output is correct
13	Correct	2 ms	256 KB	Output is correct
14	Correct	2 ms	256 KB	Output is correct
15	Correct	2 ms	384 KB	Output is correct

Subtask #2

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	256 KB	Output is correct
2	Correct	31 ms	256 KB	Output is correct
3	Correct	30 ms	396 KB	Output is correct
4	Correct	30 ms	256 KB	Output is correct
5	Correct	30 ms	384 KB	Output is correct
6	Correct	29 ms	360 KB	Output is correct
7	Correct	29 ms	256 KB	Output is correct
8	Incorrect	29 ms	384 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #3

0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	256 KB	Output is correct
2	Correct	31 ms	256 KB	Output is correct
3	Correct	30 ms	396 KB	Output is correct
4	Correct	30 ms	256 KB	Output is correct
5	Correct	30 ms	384 KB	Output is correct
6	Correct	29 ms	360 KB	Output is correct
7	Correct	29 ms	256 KB	Output is correct
8	Incorrect	29 ms	384 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #4

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	256 KB	Output is correct
2	Correct	31 ms	256 KB	Output is correct
3	Correct	30 ms	396 KB	Output is correct
4	Correct	30 ms	256 KB	Output is correct
5	Correct	30 ms	384 KB	Output is correct
6	Correct	29 ms	360 KB	Output is correct
7	Correct	29 ms	256 KB	Output is correct
8	Incorrect	29 ms	384 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	256 KB	Output is correct
2	Correct	17 ms	376 KB	Output is correct
3	Correct	18 ms	256 KB	Output is correct
4	Correct	18 ms	384 KB	Output is correct
5	Correct	18 ms	256 KB	Output is correct
6	Correct	17 ms	256 KB	Output is correct
7	Correct	18 ms	384 KB	Output is correct
8	Correct	18 ms	256 KB	Output is correct
9	Correct	17 ms	256 KB	Output is correct
10	Correct	17 ms	256 KB	Output is correct
11	Correct	2 ms	256 KB	Output is correct
12	Correct	2 ms	256 KB	Output is correct
13	Correct	2 ms	256 KB	Output is correct
14	Correct	2 ms	256 KB	Output is correct
15	Correct	2 ms	384 KB	Output is correct
16	Correct	31 ms	256 KB	Output is correct
17	Correct	31 ms	256 KB	Output is correct
18	Correct	30 ms	396 KB	Output is correct
19	Correct	30 ms	256 KB	Output is correct
20	Correct	30 ms	384 KB	Output is correct
21	Correct	29 ms	360 KB	Output is correct
22	Correct	29 ms	256 KB	Output is correct
23	Incorrect	29 ms	384 KB	Output isn't correct
24	Halted	0 ms	0 KB	-