Submission #270497

#	Time	Username	Problem	Language	Result	Execution time	Memory
270497		cgiosy	Bulldozer (JOI17_bulldozer)	C++17	75 / 100	608 ms	31992 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 {
		ll a=ll(x)*R.y, b=ll(y)*R.x;
		return a<b || a==b && (i<R.i || i==R.i && j<R.j);
	}
};
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};
	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 member function 'bool event::operator<(event) const':
bulldozer.cpp:26:42: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   26 |   return a<b || a==b && (i<R.i || i==R.i && j<R.j);
      |                                   ~~~~~~~^~~~~~~~
bulldozer.cpp:26:22: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   26 |   return a<b || a==b && (i<R.i || i==R.i && j<R.j);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:33:19: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   33 |  const int M=1<<32-__builtin_clz(N);
      |                 ~~^~~~~~~~~~~~~~~~~

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