oj.uz

Submission #26565

# Submission time Handle Problem Language Result Execution time Memory
26565 2017-07-03T06:13:34 Z Bruteforceman Bulldozer (JOI17_bulldozer) C++11
5 / 100
 28 ms 384 KB 
#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 = 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

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
bulldozer.cpp:68: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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 4 ms 256 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 4 ms 256 KB Output is correct
9 Correct 4 ms 256 KB Output is correct
10 Correct 4 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 384 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 356 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 4 ms 256 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 4 ms 256 KB Output is correct
9 Correct 4 ms 256 KB Output is correct
10 Correct 4 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 384 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 2 ms 356 KB Output is correct
16 Incorrect 28 ms 384 KB Output isn't correct
17 Halted 0 ms 0 KB -