답안 #51515 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
51515	2018-06-18T05:07:06 Z	spencercompton	Bulldozer (JOI17_bulldozer)	C++17	20 / 100	2000 ms	392 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
0 / 5.0

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

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	56 ms	256 KB	Output is correct
2	Correct	56 ms	256 KB	Output is correct
3	Correct	55 ms	256 KB	Output is correct
4	Correct	56 ms	256 KB	Output is correct
5	Correct	59 ms	384 KB	Output is correct
6	Correct	55 ms	360 KB	Output is correct
7	Correct	58 ms	392 KB	Output is correct
8	Correct	56 ms	256 KB	Output is correct
9	Correct	56 ms	384 KB	Output is correct
10	Correct	56 ms	256 KB	Output is correct
11	Correct	2 ms	384 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	384 KB	Output is correct
15	Correct	2 ms	256 KB	Output is correct
16	Correct	2 ms	256 KB	Output is correct
17	Correct	2 ms	384 KB	Output is correct
18	Correct	2 ms	256 KB	Output is correct
19	Correct	2 ms	256 KB	Output is correct
20	Correct	2 ms	256 KB	Output is correct
21	Correct	48 ms	376 KB	Output is correct
22	Correct	48 ms	256 KB	Output is correct
23	Correct	50 ms	360 KB	Output is correct
24	Correct	47 ms	256 KB	Output is correct
25	Correct	48 ms	364 KB	Output is correct
26	Correct	48 ms	360 KB	Output is correct
27	Correct	48 ms	256 KB	Output is correct
28	Correct	48 ms	356 KB	Output is correct
29	Correct	48 ms	376 KB	Output is correct
30	Correct	48 ms	356 KB	Output is correct
31	Correct	48 ms	256 KB	Output is correct
32	Correct	49 ms	364 KB	Output is correct

Subtask #3
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	56 ms	256 KB	Output is correct
2	Correct	56 ms	256 KB	Output is correct
3	Correct	55 ms	256 KB	Output is correct
4	Correct	56 ms	256 KB	Output is correct
5	Correct	59 ms	384 KB	Output is correct
6	Correct	55 ms	360 KB	Output is correct
7	Correct	58 ms	392 KB	Output is correct
8	Correct	56 ms	256 KB	Output is correct
9	Correct	56 ms	384 KB	Output is correct
10	Correct	56 ms	256 KB	Output is correct
11	Correct	2 ms	384 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	384 KB	Output is correct
15	Correct	2 ms	256 KB	Output is correct
16	Correct	2 ms	256 KB	Output is correct
17	Correct	2 ms	384 KB	Output is correct
18	Correct	2 ms	256 KB	Output is correct
19	Correct	2 ms	256 KB	Output is correct
20	Correct	2 ms	256 KB	Output is correct
21	Correct	48 ms	376 KB	Output is correct
22	Correct	48 ms	256 KB	Output is correct
23	Correct	50 ms	360 KB	Output is correct
24	Correct	47 ms	256 KB	Output is correct
25	Correct	48 ms	364 KB	Output is correct
26	Correct	48 ms	360 KB	Output is correct
27	Correct	48 ms	256 KB	Output is correct
28	Correct	48 ms	356 KB	Output is correct
29	Correct	48 ms	376 KB	Output is correct
30	Correct	48 ms	356 KB	Output is correct
31	Correct	48 ms	256 KB	Output is correct
32	Correct	49 ms	364 KB	Output is correct
33	Execution timed out	2050 ms	384 KB	Time limit exceeded
34	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	56 ms	256 KB	Output is correct
2	Correct	56 ms	256 KB	Output is correct
3	Correct	55 ms	256 KB	Output is correct
4	Correct	56 ms	256 KB	Output is correct
5	Correct	59 ms	384 KB	Output is correct
6	Correct	55 ms	360 KB	Output is correct
7	Correct	58 ms	392 KB	Output is correct
8	Correct	56 ms	256 KB	Output is correct
9	Correct	56 ms	384 KB	Output is correct
10	Correct	56 ms	256 KB	Output is correct
11	Correct	2 ms	384 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	384 KB	Output is correct
15	Correct	2 ms	256 KB	Output is correct
16	Correct	2 ms	256 KB	Output is correct
17	Correct	2 ms	384 KB	Output is correct
18	Correct	2 ms	256 KB	Output is correct
19	Correct	2 ms	256 KB	Output is correct
20	Correct	2 ms	256 KB	Output is correct
21	Correct	48 ms	376 KB	Output is correct
22	Correct	48 ms	256 KB	Output is correct
23	Correct	50 ms	360 KB	Output is correct
24	Correct	47 ms	256 KB	Output is correct
25	Correct	48 ms	364 KB	Output is correct
26	Correct	48 ms	360 KB	Output is correct
27	Correct	48 ms	256 KB	Output is correct
28	Correct	48 ms	356 KB	Output is correct
29	Correct	48 ms	376 KB	Output is correct
30	Correct	48 ms	356 KB	Output is correct
31	Correct	48 ms	256 KB	Output is correct
32	Correct	49 ms	364 KB	Output is correct
33	Execution timed out	2050 ms	384 KB	Time limit exceeded
34	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

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

답안 #51515

Compilation message

Subtask #1 0 / 5.0

Subtask #2 20.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
20.0 / 20.0

Subtask #3
0 / 35.0

Subtask #4
0 / 20.0

Subtask #5
0 / 20.0