답안 #51520 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
51520	2018-06-18T05:23:19 Z	spencercompton	Bulldozer (JOI17_bulldozer)	C++17	20 / 100	2000 ms	512 KB

bulldozer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
long double ptLineDist(long double x1, long double y1, long double x2, long double y2, long double px, long double py){
	long double pd2 = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
	long double x, y;
	if(pd2 == 0){
		x = x1;
		y = y2;
	}
	else{
		long 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];
	}
	long double tol = 0.0000000000000001L;
	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<long double, ll> > li;
			for(int k = 0; k<n; k++){
				bool cross = (y[k]+dx)*(dy-0LL) > (-dx-0LL)*(x[k]-dy);
				long 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;
			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<long double, ll> > li;
			for(int k = 0; k<n; k++){
				bool cross = (y[k]+dx)*(dy-0LL) > (-dx-0LL)*(x[k]-dy);
				long 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;
			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	Correct	77 ms	376 KB	Output is correct
2	Correct	77 ms	384 KB	Output is correct
3	Correct	76 ms	256 KB	Output is correct
4	Correct	77 ms	364 KB	Output is correct
5	Correct	75 ms	376 KB	Output is correct
6	Correct	75 ms	256 KB	Output is correct
7	Correct	76 ms	252 KB	Output is correct
8	Correct	76 ms	256 KB	Output is correct
9	Correct	74 ms	256 KB	Output is correct
10	Correct	76 ms	384 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	Incorrect	2 ms	256 KB	Output isn't correct

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	93 ms	364 KB	Output is correct
2	Correct	92 ms	256 KB	Output is correct
3	Correct	92 ms	384 KB	Output is correct
4	Correct	92 ms	376 KB	Output is correct
5	Correct	93 ms	384 KB	Output is correct
6	Correct	91 ms	256 KB	Output is correct
7	Correct	92 ms	364 KB	Output is correct
8	Correct	92 ms	360 KB	Output is correct
9	Correct	91 ms	256 KB	Output is correct
10	Correct	93 ms	400 KB	Output is correct
11	Correct	1 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	256 KB	Output is correct
17	Correct	2 ms	256 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	81 ms	256 KB	Output is correct
22	Correct	81 ms	376 KB	Output is correct
23	Correct	81 ms	376 KB	Output is correct
24	Correct	81 ms	360 KB	Output is correct
25	Correct	81 ms	360 KB	Output is correct
26	Correct	81 ms	412 KB	Output is correct
27	Correct	82 ms	360 KB	Output is correct
28	Correct	81 ms	384 KB	Output is correct
29	Correct	81 ms	376 KB	Output is correct
30	Correct	81 ms	384 KB	Output is correct
31	Correct	81 ms	256 KB	Output is correct
32	Correct	85 ms	404 KB	Output is correct

Subtask #3
0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	93 ms	364 KB	Output is correct
2	Correct	92 ms	256 KB	Output is correct
3	Correct	92 ms	384 KB	Output is correct
4	Correct	92 ms	376 KB	Output is correct
5	Correct	93 ms	384 KB	Output is correct
6	Correct	91 ms	256 KB	Output is correct
7	Correct	92 ms	364 KB	Output is correct
8	Correct	92 ms	360 KB	Output is correct
9	Correct	91 ms	256 KB	Output is correct
10	Correct	93 ms	400 KB	Output is correct
11	Correct	1 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	256 KB	Output is correct
17	Correct	2 ms	256 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	81 ms	256 KB	Output is correct
22	Correct	81 ms	376 KB	Output is correct
23	Correct	81 ms	376 KB	Output is correct
24	Correct	81 ms	360 KB	Output is correct
25	Correct	81 ms	360 KB	Output is correct
26	Correct	81 ms	412 KB	Output is correct
27	Correct	82 ms	360 KB	Output is correct
28	Correct	81 ms	384 KB	Output is correct
29	Correct	81 ms	376 KB	Output is correct
30	Correct	81 ms	384 KB	Output is correct
31	Correct	81 ms	256 KB	Output is correct
32	Correct	85 ms	404 KB	Output is correct
33	Execution timed out	2025 ms	512 KB	Time limit exceeded
34	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	93 ms	364 KB	Output is correct
2	Correct	92 ms	256 KB	Output is correct
3	Correct	92 ms	384 KB	Output is correct
4	Correct	92 ms	376 KB	Output is correct
5	Correct	93 ms	384 KB	Output is correct
6	Correct	91 ms	256 KB	Output is correct
7	Correct	92 ms	364 KB	Output is correct
8	Correct	92 ms	360 KB	Output is correct
9	Correct	91 ms	256 KB	Output is correct
10	Correct	93 ms	400 KB	Output is correct
11	Correct	1 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	256 KB	Output is correct
17	Correct	2 ms	256 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	81 ms	256 KB	Output is correct
22	Correct	81 ms	376 KB	Output is correct
23	Correct	81 ms	376 KB	Output is correct
24	Correct	81 ms	360 KB	Output is correct
25	Correct	81 ms	360 KB	Output is correct
26	Correct	81 ms	412 KB	Output is correct
27	Correct	82 ms	360 KB	Output is correct
28	Correct	81 ms	384 KB	Output is correct
29	Correct	81 ms	376 KB	Output is correct
30	Correct	81 ms	384 KB	Output is correct
31	Correct	81 ms	256 KB	Output is correct
32	Correct	85 ms	404 KB	Output is correct
33	Execution timed out	2025 ms	512 KB	Time limit exceeded
34	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	77 ms	376 KB	Output is correct
2	Correct	77 ms	384 KB	Output is correct
3	Correct	76 ms	256 KB	Output is correct
4	Correct	77 ms	364 KB	Output is correct
5	Correct	75 ms	376 KB	Output is correct
6	Correct	75 ms	256 KB	Output is correct
7	Correct	76 ms	252 KB	Output is correct
8	Correct	76 ms	256 KB	Output is correct
9	Correct	74 ms	256 KB	Output is correct
10	Correct	76 ms	384 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	Incorrect	2 ms	256 KB	Output isn't correct

답안 #51520

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