Submission #26578

#	Time	Username	Problem	Language	Result	Execution time	Memory
26578		Bruteforceman	Bulldozer (JOI17_bulldozer)	C++11	25 / 100	2017 ms	468 KiB

bulldozer

#include <bits/stdc++.h>
using namespace std;

int X[2005];
int Y[2005];
int C[2005];
int n;

double project(int p, double m) {
	return (-Y[p] / m) + X[p]; 
}
long long solve(int p, int q) {
	if(X[p] == X[q]) return 0;
	if(Y[p] == Y[q]) return 0;
	if(X[p] > X[q]) swap(p, q);
	double m = ((double)(Y[q] - Y[p])) / (X[q] - X[p]);
	
	double pos = project(p, m);
	
	vector <pair <double, int> > U, V;
	for(int i = 1; i <= n; i++) {
		double pp = project(i, m);
		if(i == p || i == q) continue;
		if(pp < pos) {
			U.push_back(make_pair(pp, C[i]));
		} else {
			V.push_back(make_pair(pp, C[i]));
		}
	}
	sort(U.begin(), U.end());
	sort(V.begin(), V.end());
	reverse(U.begin(), U.end());
	
	long long s1 = max(C[p], max(C[q], C[p] + C[q]));
	long long s2 = s1;
	long long ans = s1;
	
	for(auto i : U) {
		// cout << i.first << " " << i.second << endl;
		s1 += i.second;
		ans = max(ans, s1);
	}
	for(auto i : V) {
		s2 += i.second;
		ans = max(ans, s2);

	}
	return ans;
}

long long hehe(int x, int y) {
	long long ans = 0;
	for(int i = 1; i <= n; i++) {
		if(x <= X[i] && X[i] <= y) {
			ans += C[i];
		}
	}
	return ans;
}


int main() {
	scanf("%d", &n);
	bool good = true;
	for(int i = 1; i <= n; i++) {
		scanf("%d %d %d", &X[i], &Y[i], &C[i]);
		good &= (Y[i] == 0);
	}
	
	if(good) {
		long long res = 0;
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				if(X[i] <= X[j]) {
					res = max(res, hehe(X[i], X[j]));
				}
			}
		}
		cout << res << endl;
		exit(0);
	}
	
	long long sum = 0;
	for(int i = 1; i <= n; i++) {
		sum += C[i];
	}
	long long ans = 0;
	for(int i = 1; i <= n; i++) {
		ans = max(ans, 1LL * C[i]);
	}
	ans = max(ans, sum);
	for(int i = 1; i <= n; i++) {
		for(int j = i + 1; j <= n; j++) {
			ans = max(ans, solve(i, j));
		}
	}
	cout << ans << endl;
	return 0;
}

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
bulldozer.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &X[i], &Y[i], &C[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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