답안 #51519 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
51519	2018-06-18T05:22:38 Z	spencercompton	Bulldozer (JOI17_bulldozer)	C++17	20 / 100	2000 ms	504 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	78 ms	376 KB	Output is correct
2	Correct	81 ms	384 KB	Output is correct
3	Correct	79 ms	256 KB	Output is correct
4	Correct	75 ms	384 KB	Output is correct
5	Correct	76 ms	256 KB	Output is correct
6	Correct	76 ms	384 KB	Output is correct
7	Correct	76 ms	360 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	384 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	92 ms	256 KB	Output is correct
2	Correct	91 ms	256 KB	Output is correct
3	Correct	92 ms	364 KB	Output is correct
4	Correct	93 ms	256 KB	Output is correct
5	Correct	93 ms	256 KB	Output is correct
6	Correct	92 ms	384 KB	Output is correct
7	Correct	95 ms	376 KB	Output is correct
8	Correct	95 ms	256 KB	Output is correct
9	Correct	93 ms	400 KB	Output is correct
10	Correct	93 ms	376 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	384 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	364 KB	Output is correct
22	Correct	80 ms	256 KB	Output is correct
23	Correct	80 ms	396 KB	Output is correct
24	Correct	80 ms	364 KB	Output is correct
25	Correct	80 ms	504 KB	Output is correct
26	Correct	80 ms	256 KB	Output is correct
27	Correct	82 ms	376 KB	Output is correct
28	Correct	82 ms	256 KB	Output is correct
29	Correct	80 ms	256 KB	Output is correct
30	Correct	82 ms	376 KB	Output is correct
31	Correct	83 ms	256 KB	Output is correct
32	Correct	83 ms	256 KB	Output is correct

Subtask #3
0 / 35.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	78 ms	376 KB	Output is correct
2	Correct	81 ms	384 KB	Output is correct
3	Correct	79 ms	256 KB	Output is correct
4	Correct	75 ms	384 KB	Output is correct
5	Correct	76 ms	256 KB	Output is correct
6	Correct	76 ms	384 KB	Output is correct
7	Correct	76 ms	360 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	384 KB	Output is correct
14	Correct	2 ms	256 KB	Output is correct
15	Incorrect	2 ms	256 KB	Output isn't correct

답안 #51519

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