oj.uz

답안 #51409

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
51409 2018-06-18T00:22:42 Z spencercompton Bulldozer (JOI17_bulldozer) C++17
0 / 100
 35 ms 396 KB 
#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 sqrt((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++){
				ll cross = 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<=0LL){
					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-7){
					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;
}

Compilation message

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:34:22: warning: operation on 'cross' may be undefined [-Wsequence-point]
     ll cross = cross = (y[k]-y[j])*(x[j]-x[i]) - (y[j]-y[i])*(x[k]-x[j]);
                ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 256 KB Output is correct
2 Correct 32 ms 356 KB Output is correct
3 Correct 32 ms 384 KB Output is correct
4 Correct 30 ms 256 KB Output is correct
5 Correct 32 ms 396 KB Output is correct
6 Correct 30 ms 384 KB Output is correct
7 Correct 30 ms 376 KB Output is correct
8 Incorrect 31 ms 376 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 256 KB Output is correct
2 Correct 32 ms 356 KB Output is correct
3 Correct 32 ms 384 KB Output is correct
4 Correct 30 ms 256 KB Output is correct
5 Correct 32 ms 396 KB Output is correct
6 Correct 30 ms 384 KB Output is correct
7 Correct 30 ms 376 KB Output is correct
8 Incorrect 31 ms 376 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 256 KB Output is correct
2 Correct 32 ms 356 KB Output is correct
3 Correct 32 ms 384 KB Output is correct
4 Correct 30 ms 256 KB Output is correct
5 Correct 32 ms 396 KB Output is correct
6 Correct 30 ms 384 KB Output is correct
7 Correct 30 ms 376 KB Output is correct
8 Incorrect 31 ms 376 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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