Submission #270473

#	Time	Username	Problem	Language	Result	Execution time	Memory
270473		cgiosy	Bulldozer (JOI17_bulldozer)	C++17	100 / 100	592 ms	47480 KiB

bulldozer

#include <bits/stdc++.h>
using namespace std;
using ll=long long;

struct node {
	ll mx, lm, rm, sum;
	node operator+(const node R) const {
		return {
			max({mx, R.mx, rm+R.lm}),
			max(lm, sum+R.lm),
			max(R.rm, rm+R.sum),
			sum+R.sum
		};
	}
};
struct spot {
	int x, y, w;
	bool operator<(const spot R) const {
		return x<R.x || x==R.x && y<R.y;
	}
};
struct event {
	int x, y, i, j;
	bool operator<(const event R) const {
		return ll(x)*R.y<ll(y)*R.x;
	}
};
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	int N, K=0;
	cin>>N;
	const int M=1<<32-__builtin_clz(N);
	vector<spot> A(N);
	for(auto&[x,y,w]:A) cin>>x>>y>>w;
	sort(begin(A), end(A));

	vector<event> E(N*(N-1)/2);
	for(int i=0; i<N; i++) for(int j=0; j<i; j++)
		E[K++]={A[i].x-A[j].x, A[i].y-A[j].y, j, i};
	stable_sort(begin(E), end(E));

	vector<node> T(M*2);
	auto upd=[&](int i, int x) {
		for(T[i+=M]={x, x, x, x}; i>>=1;)
			T[i]=T[i*2]+T[i*2+1];
	};
	for(int i=0; i<N; i++) {
		int x=A[i].w;
		T[i+M]={x, x, x, x};
	}
	for(int i=M; i--;)
		T[i]=T[i*2]+T[i*2+1];

	ll mx=T[1].mx;
	vector<int> P(N);
	iota(begin(P), end(P), 0);
	for(int k=0; k<K; k++) {
		auto[x,y,i,j]=E[k];
		swap(P[i], P[j]);
		upd(P[i], A[i].w);
		upd(P[j], A[j].w);
		if(k+1<K && !(E[k]<E[k+1])) continue;
		mx=max(mx, T[1].mx);
	}
	cout<<max(mx, ll(0))<<'\n';
}

Compilation message (stderr)

bulldozer.cpp: In member function 'bool spot::operator<(spot) const':
bulldozer.cpp:19:26: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   19 |   return x<R.x || x==R.x && y<R.y;
      |                   ~~~~~~~^~~~~~~~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:32:19: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   32 |  const int M=1<<32-__builtin_clz(N);
      |                 ~~^~~~~~~~~~~~~~~~~

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