Submission #514268

#	Time	Username	Problem	Language	Result	Execution time	Memory
514268		amunduzbaev	Bulldozer (JOI17_bulldozer)	C++14	20 / 100	2086 ms	66144 KiB

bulldozer

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

#define ar array
#define int long long

long double const eps = 1e-18;

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];
	} sort(a.begin(), a.end());
	
	vector<pair<long double, pair<int, int>>> tt;
	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[j][1] - a[i][1]) * 1. / (a[i][0] - a[j][0]);
			tt.push_back({slop, {i, j}});
		}
	}
	
	vector<long double> b(n);
	vector<int> p(n); iota(p.begin(), p.end(), 0);
	for(int i=0;i<n;i++){
		b[i] = a[i][1] * 1. - (a[i][0] * -2e9);
	}
	
	sort(p.begin(), p.end(), [&](int i, int j){
		return (eps < b[j] - b[i]);
	});
	
	vector<int> pos(n);
	for(int i=0;i<n;i++) pos[p[i]] = i;

	int res = 0;
	sort(tt.begin(), tt.end());
	auto check = [&](){
		int pref = 0, mn = 0;
		for(int i=0;i<n;i++){
			pref += a[p[i]][2];
			res = max(res, pref - mn);
			mn = min(mn, pref);
		}
	};
	check();
	for(auto s : tt){
		auto [i, j] = s.second;
		
		assert(abs(pos[i] - pos[j]) == 1);
		swap(p[pos[i]], p[pos[j]]);
		swap(pos[i], pos[j]);
		check();
	}
	
	cout<<res<<"\n";
}

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:52:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |   auto [i, j] = s.second;
      |        ^

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