Submission #51511

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
51511	2018-06-18T04:59:26 Z	spencercompton	Bulldozer (JOI17_bulldozer)	C++17	5 / 100	34 ms	384 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-7;
			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	19 ms	256 KB	Output is correct
3	Correct	19 ms	256 KB	Output is correct
4	Correct	18 ms	360 KB	Output is correct
5	Correct	17 ms	256 KB	Output is correct
6	Correct	17 ms	256 KB	Output is correct
7	Correct	18 ms	256 KB	Output is correct
8	Correct	18 ms	256 KB	Output is correct
9	Correct	18 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	356 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	34 ms	360 KB	Output is correct
2	Correct	30 ms	360 KB	Output is correct
3	Correct	29 ms	256 KB	Output is correct
4	Correct	30 ms	384 KB	Output is correct
5	Correct	30 ms	256 KB	Output is correct
6	Correct	29 ms	384 KB	Output is correct
7	Correct	29 ms	256 KB	Output is correct
8	Incorrect	29 ms	356 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #3

0 / 35.0

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

Subtask #4

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	34 ms	360 KB	Output is correct
2	Correct	30 ms	360 KB	Output is correct
3	Correct	29 ms	256 KB	Output is correct
4	Correct	30 ms	384 KB	Output is correct
5	Correct	30 ms	256 KB	Output is correct
6	Correct	29 ms	384 KB	Output is correct
7	Correct	29 ms	256 KB	Output is correct
8	Incorrect	29 ms	356 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	19 ms	256 KB	Output is correct
3	Correct	19 ms	256 KB	Output is correct
4	Correct	18 ms	360 KB	Output is correct
5	Correct	17 ms	256 KB	Output is correct
6	Correct	17 ms	256 KB	Output is correct
7	Correct	18 ms	256 KB	Output is correct
8	Correct	18 ms	256 KB	Output is correct
9	Correct	18 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	356 KB	Output is correct
15	Correct	2 ms	384 KB	Output is correct
16	Correct	34 ms	360 KB	Output is correct
17	Correct	30 ms	360 KB	Output is correct
18	Correct	29 ms	256 KB	Output is correct
19	Correct	30 ms	384 KB	Output is correct
20	Correct	30 ms	256 KB	Output is correct
21	Correct	29 ms	384 KB	Output is correct
22	Correct	29 ms	256 KB	Output is correct
23	Incorrect	29 ms	356 KB	Output isn't correct
24	Halted	0 ms	0 KB	-