Submission #270451

#	Time	Username	Problem	Language	Result	Execution time	Memory
270451		cgiosy	Bulldozer (JOI17_bulldozer)	C++17	80 / 100	595 ms	31996 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 point { int x, 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;
	cin>>N;
	const int M=1<<32-__builtin_clz(N), K=N*(N-1)/2;
	vector<point> A(N);
	vector<int> W(N), P(N), X(N);
	for(int i=0; i<N; i++)
		cin>>A[i].x>>A[i].y>>W[i];
	iota(begin(X), end(X), 0);
	sort(begin(X), end(X), [&](int i, int j) {
		return A[i].x<A[j].x || A[i].x==A[j].x && A[i].y<A[j].y;
	});
	for(int i=0; i<N; i++) P[X[i]]=i;
	decltype(X)().swap(X);

	vector<event> E(K);
	for(int i=0, k=0; i<N; i++) for(int j=0; j<i; j++) {
		int x=A[i].x-A[j].x, y=A[i].y-A[j].y;
		if(x<0 || !x && y<0) x=-x, y=-y;
		E[k++]={x, y, i, j};
	}
	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=W[i];
		T[P[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;
	for(int k=0; k<K; k++) {
		auto[x,y,i,j]=E[k];
		swap(P[i], P[j]);
		upd(P[i], W[i]);
		upd(P[j], W[j]);
		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 function 'int main()':
bulldozer.cpp:27:19: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   27 |  const int M=1<<32-__builtin_clz(N), K=N*(N-1)/2;
      |                 ~~^~~~~~~~~~~~~~~~~
bulldozer.cpp: In lambda function:
bulldozer.cpp:34:42: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   34 |   return A[i].x<A[j].x || A[i].x==A[j].x && A[i].y<A[j].y;
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:42:16: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   42 |   if(x<0 || !x && y<0) x=-x, y=-y;
      |             ~~~^~~~~~

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