제출 #51508

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
51508		spencercompton	Bulldozer (JOI17_bulldozer)	C++17	0 / 100	32 ms	376 KiB

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++){
			vector<pair<double, ll> > li;
			for(int k = 0; k<n; k++){
				bool cross = (y[k]-y[j])*(x[j]-x[i]) > (y[j]-y[i])*(x[k]-x[j]);
				double dist = ptLineDist(x[i], y[i], x[j], y[j], 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());
			int f = -1;
			int s = -1;
			for(int k = 0; k<n; k++){
				if(abs(li[k].first)<1e-9){
					if(f==-1) {
						f = k;
					}
					s = k;
				}
			}
			assert(f!=-1);
			ll bestPre = 0LL;
			ll curPre = 0LL;
			for(int k = f-1; k>=0; k--){
				curPre += li[k].second;
				bestPre = max(bestPre,curPre);
			}
			ll bestPost = 0LL;
			ll curPost = 0LL;
			for(int k = s+1; k<n; k++){
				curPost += li[k].second;
				bestPost = max(bestPost,curPost);
			}
			ans = max(ans,v[i]+v[j]+bestPre+bestPost);
		}
	}
	cout << ans << endl;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 20
• Subtask 3: 0 / 35
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20