oj.uz

Submission #514174

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

#define ar array
#define int long long

long double const eps = 1e-15;

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<long 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 21 ms 588 KB Output is correct
2 Correct 19 ms 588 KB Output is correct
3 Correct 19 ms 588 KB Output is correct
4 Correct 18 ms 588 KB Output is correct
5 Correct 20 ms 716 KB Output is correct
6 Correct 19 ms 716 KB Output is correct
7 Correct 18 ms 588 KB Output is correct
8 Correct 18 ms 588 KB Output is correct
9 Incorrect 21 ms 588 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
0 / 35.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 588 KB Output is correct
2 Correct 19 ms 588 KB Output is correct
3 Correct 19 ms 588 KB Output is correct
4 Correct 18 ms 588 KB Output is correct
5 Correct 20 ms 716 KB Output is correct
6 Correct 19 ms 716 KB Output is correct
7 Correct 18 ms 588 KB Output is correct
8 Correct 18 ms 588 KB Output is correct
9 Incorrect 21 ms 588 KB Output isn't correct
10 Halted 0 ms 0 KB -