제출 #514181

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
514181		amunduzbaev	Bulldozer (JOI17_bulldozer)	C++14	0 / 100	30 ms	716 KiB

bulldozer

#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);
		}
	}
	
	int res = -1e18;
	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
• Subtask 2: 0 / 20
• Subtask 3: 0 / 35
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20