Submission #943343

#	Time	Username	Problem	Language	Result	Execution time	Memory
943343		HIR180	Bulldozer (JOI17_bulldozer)	C++17	100 / 100	516 ms	35520 KiB

bulldozer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rng(i,a,b) for(int i=(int)a;i<(int)b;i++)
#define rep(i,b) rng(i,0,b)
#define repn(i,b) rng(i,1,b+1)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define si(x) (int)(x.size())
#define mp make_pair

#define tct template<class t>
tct using vc=vector<t>;
using vi=vc<int>;
#define tctu template<class t,class u>
tctu bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;}
tctu bool chmin(t&a,u b){if(a>b){a=b;return true;}else return false;}

using P=pair<int,int>;
#define mp make_pair
#define a first
#define b second
using ld = long double;
constexpr int mod = 998244353;

void solve(){
	int n;cin>>n;
	vc<pair<P,int>>vec(n);
	rep(i,n){
		int x,y,w;cin>>x>>y>>w;
		vec[i] = mp(mp(x, y), w);
	}
	sort(all(vec), [](auto&a, auto&b){
		if(a.a.a != b.a.a) return a.a.a < b.a.a;
		return a.a.b < b.a.b;
	});
	vc<pair<P,P>>dir;
	rep(i,n){
		rng(j,i+1,n){
			if(vec[i].a.a == vec[j].a.a) continue;
			dir.eb(mp(vec[j].a.a-vec[i].a.a, vec[j].a.b-vec[i].a.b), mp(i, j));
		}
	}
	vc<int>p(n),ran(n);
	rep(i,n) p[i] = ran[i] = i;
	sort(all(dir), [](auto &a,auto &b){
		ll f = (ll)a.a.a*b.a.b-(ll)a.a.b*b.a.a;
		if(f) return f > 0;
		else return a.b < b.b;
	});
	int nn = 1;
	while(nn <= n) nn <<= 1;
	
	vc<ll>seg(2*nn), sum(2*nn), le(2*nn), ri(2*nn);
	auto mrg=[&](int k){
		sum[k] = sum[k*2+1]+sum[k*2+2];
		le[k] = max(le[k*2+1], sum[k*2+1]+le[k*2+2]);
		ri[k] = max(ri[k*2+2], sum[k*2+2]+ri[k*2+1]);
		seg[k] = max(max(seg[k*2+1],seg[k*2+2]),le[k*2+2]+ri[k*2+1]);
	};
	auto upd=[&](int pos, int v){
		pos += nn-1;
		sum[pos] = v;
		le[pos] = ri[pos] = seg[pos] = max(0, v);
		while(pos){
			pos = (pos-1)/2;
			mrg(pos);
		}
	};
	rep(i,n){
		upd(i, vec[p[i]].b);
	}
	ll ans = seg[0];
	rep(i,si(dir)){
		int x = dir[i].b.a, y = dir[i].b.b;
		if(ran[x] < ran[y]){
			swap(p[ran[x]], p[ran[y]]);
			swap(ran[x], ran[y]);
			upd(ran[x], vec[p[ran[x]]].b);
			upd(ran[y], vec[p[ran[y]]].b);
		}
		if(i+1 == si(dir) or (ll)dir[i].a.a*dir[i+1].a.b != (ll)dir[i].a.b*dir[i+1].a.a){
			chmax(ans, seg[0]);
		}
	}
	cout << ans << '\n';
		
}
signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	int t; t=1;//cin>>t;
	while(t--) solve();
}

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