답안 #51516 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
51516	2018-06-18T05:08:01 Z	spencercompton	Bulldozer (JOI17_bulldozer)	C++17	0 / 100	66 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 = 1e-16;
			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 = 1e-16;
			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
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	51 ms	256 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	59 ms	360 KB	Output is correct
2	Correct	58 ms	376 KB	Output is correct
3	Correct	57 ms	304 KB	Output is correct
4	Correct	58 ms	256 KB	Output is correct
5	Correct	66 ms	256 KB	Output is correct
6	Correct	58 ms	384 KB	Output is correct
7	Correct	58 ms	256 KB	Output is correct
8	Correct	63 ms	396 KB	Output is correct
9	Correct	57 ms	256 KB	Output is correct
10	Correct	58 ms	256 KB	Output is correct
11	Correct	2 ms	256 KB	Output is correct
12	Correct	2 ms	384 KB	Output is correct
13	Correct	2 ms	384 KB	Output is correct
14	Correct	2 ms	256 KB	Output is correct
15	Correct	2 ms	256 KB	Output is correct
16	Correct	2 ms	384 KB	Output is correct
17	Correct	2 ms	356 KB	Output is correct
18	Correct	2 ms	392 KB	Output is correct
19	Correct	2 ms	384 KB	Output is correct
20	Correct	2 ms	256 KB	Output is correct
21	Correct	48 ms	256 KB	Output is correct
22	Correct	48 ms	256 KB	Output is correct
23	Correct	49 ms	384 KB	Output is correct
24	Correct	48 ms	256 KB	Output is correct
25	Incorrect	49 ms	376 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Subtask #3
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	59 ms	360 KB	Output is correct
2	Correct	58 ms	376 KB	Output is correct
3	Correct	57 ms	304 KB	Output is correct
4	Correct	58 ms	256 KB	Output is correct
5	Correct	66 ms	256 KB	Output is correct
6	Correct	58 ms	384 KB	Output is correct
7	Correct	58 ms	256 KB	Output is correct
8	Correct	63 ms	396 KB	Output is correct
9	Correct	57 ms	256 KB	Output is correct
10	Correct	58 ms	256 KB	Output is correct
11	Correct	2 ms	256 KB	Output is correct
12	Correct	2 ms	384 KB	Output is correct
13	Correct	2 ms	384 KB	Output is correct
14	Correct	2 ms	256 KB	Output is correct
15	Correct	2 ms	256 KB	Output is correct
16	Correct	2 ms	384 KB	Output is correct
17	Correct	2 ms	356 KB	Output is correct
18	Correct	2 ms	392 KB	Output is correct
19	Correct	2 ms	384 KB	Output is correct
20	Correct	2 ms	256 KB	Output is correct
21	Correct	48 ms	256 KB	Output is correct
22	Correct	48 ms	256 KB	Output is correct
23	Correct	49 ms	384 KB	Output is correct
24	Correct	48 ms	256 KB	Output is correct
25	Incorrect	49 ms	376 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	59 ms	360 KB	Output is correct
2	Correct	58 ms	376 KB	Output is correct
3	Correct	57 ms	304 KB	Output is correct
4	Correct	58 ms	256 KB	Output is correct
5	Correct	66 ms	256 KB	Output is correct
6	Correct	58 ms	384 KB	Output is correct
7	Correct	58 ms	256 KB	Output is correct
8	Correct	63 ms	396 KB	Output is correct
9	Correct	57 ms	256 KB	Output is correct
10	Correct	58 ms	256 KB	Output is correct
11	Correct	2 ms	256 KB	Output is correct
12	Correct	2 ms	384 KB	Output is correct
13	Correct	2 ms	384 KB	Output is correct
14	Correct	2 ms	256 KB	Output is correct
15	Correct	2 ms	256 KB	Output is correct
16	Correct	2 ms	384 KB	Output is correct
17	Correct	2 ms	356 KB	Output is correct
18	Correct	2 ms	392 KB	Output is correct
19	Correct	2 ms	384 KB	Output is correct
20	Correct	2 ms	256 KB	Output is correct
21	Correct	48 ms	256 KB	Output is correct
22	Correct	48 ms	256 KB	Output is correct
23	Correct	49 ms	384 KB	Output is correct
24	Correct	48 ms	256 KB	Output is correct
25	Incorrect	49 ms	376 KB	Output isn't correct
26	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	51 ms	256 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

답안 #51516

Compilation message

Subtask #1 0 / 5.0

Subtask #2 0 / 20.0

Subtask #3 0 / 35.0

Subtask #4 0 / 20.0

Subtask #5 0 / 20.0

Subtask #1
0 / 5.0

Subtask #2
0 / 20.0

Subtask #3
0 / 35.0

Subtask #4
0 / 20.0

Subtask #5
0 / 20.0