Submission #270520

#	Time	Username	Problem	Language	Result	Execution time	Memory
270520		cgiosy	Bulldozer (JOI17_bulldozer)	C++17	100 / 100	619 ms	24184 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;
	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;
	}
};
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	int N, K=0;
	cin>>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, i<<16|j};
	sort(begin(E), end(E));

	vector<node> T(4096);
	auto upd=[&](int i, int x) {
		for(T[i|=2048]={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+2048]={x, x, x, x};
	}
	for(int i=2048; 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,t]=E[k];
		int i=t>>16, j=t&65535;
		swap(P[i], P[j]);
		upd(P[i], A[i].w);
		upd(P[j], A[j].w);
		if(k+1<K && ll(E[k].x)*E[k+1].y==ll(E[k+1].x)*E[k].y) continue;
		mx=max(mx, T[1].mx);
	}
	cout<<mx<<'\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:22: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   26 |   return a<b || a==b && i<R.i;
      |                 ~~~~~^~~~~~~~

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