oj.uz

Submission #514172

# Submission time Handle Problem Language Result Execution time Memory
514172 2022-01-18T04:49:50 Z amunduzbaev Bulldozer (JOI17_bulldozer) C++14
0 / 100
 27 ms 568 KB 
#include "bits/stdc++.h"
using namespace std;

#define ar array
#define int long long

double const eps = 1e-9;

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	vector<ar<int, 3>> a(n);
	for(int i=0;i<n;i++){
		cin>>a[i][0]>>a[i][1]>>a[i][2];
	}
	
	vector<double> tt;
	tt.push_back(2e9);
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(a[i][0] == a[j][0]) continue;
			double slop = (a[i][1] - a[j][1]) / (a[i][0] - a[j][0]);
			tt.push_back(slop);
			tt.push_back(slop + eps);
			tt.push_back(slop - eps);
		}
	}
	
	sort(tt.begin(), tt.end());
	int res = 0;
	for(auto s : tt){
		vector<double> b(n);
		vector<int> p(n);
		for(int i=0;i<n;i++){
			b[i] = a[i][1] - a[i][0] * s;
			p[i] = i;
		}
		
		sort(p.begin(), p.end(), [&](int i, int j){
			return (eps < b[j] - b[i]);
		});
		
		int mn = 0, pref = 0;
		for(int i=0;i<n;i++){
			pref += a[p[i]][2];
			if(i+1 == n || b[p[i]] != b[p[i+1]]){
				res = max(res, pref - mn);
			} mn = min(mn, pref);
		}
	}
	
	cout<<res<<"\n";
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 460 KB Output is correct
2 Correct 18 ms 552 KB Output is correct
3 Correct 17 ms 564 KB Output is correct
4 Correct 17 ms 460 KB Output is correct
5 Correct 27 ms 460 KB Output is correct
6 Correct 22 ms 460 KB Output is correct
7 Correct 17 ms 460 KB Output is correct
8 Correct 19 ms 560 KB Output is correct
9 Incorrect 19 ms 460 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
0 / 35.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 460 KB Output is correct
2 Correct 18 ms 552 KB Output is correct
3 Correct 17 ms 564 KB Output is correct
4 Correct 17 ms 460 KB Output is correct
5 Correct 27 ms 460 KB Output is correct
6 Correct 22 ms 460 KB Output is correct
7 Correct 17 ms 460 KB Output is correct
8 Correct 19 ms 560 KB Output is correct
9 Incorrect 19 ms 460 KB Output isn't correct
10 Halted 0 ms 0 KB -