Submission #514566

#	Time	Username	Problem	Language	Result	Execution time	Memory
514566		amunduzbaev	Bulldozer (JOI17_bulldozer)	C++14	75 / 100	1006 ms	66208 KiB

bulldozer

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
#define int long long
 
const int N = 2005;
long double const eps = 1e-14;
 
struct ST{
	ar<int, 4> tree[N * 4];
	void merge(ar<int, 4>& x, ar<int, 4>& a, ar<int, 4>& b){
		x[0] = max({a[0], b[0], a[2] + b[1]});
		x[1] = max({a[1], a[3] + b[1]});
		x[2] = max({b[2], b[3] + a[2]});
		x[3] = a[3] + b[3];
	}
	
	void sett(int i, int v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx){ 
			tree[x] = {max(v, 0ll), max(v, 0ll), max(v, 0ll), v}; return;
		} int m = (lx + rx) >> 1;
		if(i <= m) sett(i, v, lx, m, x<<1);
		else sett(i, v, m+1, rx, x<<1|1);
		merge(tree[x], tree[x<<1], tree[x<<1|1]);
	}
	
	int get(int i, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) return tree[x][3];
		int m = (lx + rx) >> 1;
		if(i <= m) return get(i, lx, m, x<<1);
		else return get(i, m+1, rx, x<<1|1);
	}
}tree;
 
/*
 
6
0 1 10
0 5 10
3 0 10
3 3 -5
4 5 10
4 1 10
 
*/
 
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(), [&](auto& a, auto& b){
		if(a[0] != b[0]) return a[0] < b[0];
		return a[1] > b[1];
	});
	//~ cout<<"\n";
	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]);
			//~ cout<<i<<" "<<j<<" "<<slop<<"\n";
			tt.push_back({slop, {i, j}});
		}
	}
	
	vector<long double> b(n);
	vector<int> p(n); iota(p.begin(), p.end(), 0);
	
	vector<int> pos(n);
	for(int i=0;i<n;i++) pos[p[i]] = i, tree.sett(i, a[p[i]][2]);
	int res = tree.tree[1][0];
	sort(tt.begin(), tt.end(), [&](auto& a, auto& b){
		return (eps < b.first - a.first);
	});
	
	vector<int> used(n);
	
	for(int l=0;l<(int)tt.size();){
		int k = l;
		//~ cout<<tt[l].first<<"\n";
		while(k < (int)tt.size() && abs(tt[l].first - tt[k].first) < eps){
			auto [i, j] = tt[k].second; k++;
			//~ if(used[j]) continue;
			//~ used[j] = 1;
			//~ cout<<i<<" "<<j<<" "<<pos[i]<<" "<<pos[j]<<"\n";
			swap(p[pos[i]], p[pos[j]]);
			swap(pos[i], pos[j]);
			tree.sett(pos[i], a[i][2]), tree.sett(pos[j], a[j][2]);
			//~ k++;
		} //while(l < k) used[tt[l].second.second] = 0, l++;
		l = k;
		//~ for(int i=0;i<n;i++){
			//~ cout<<p[i]<<" ";
		//~ } cout<<"\n";
		
		res = max(res, tree.tree[1][0]);
	}
	
	cout<<res<<"\n";
}

Compilation message (stderr)

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

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