Submission #309261

#	Time	Username	Problem	Language	Result	Execution time	Memory
309261		cgiosy	Bulldozer (JOI17_bulldozer)	C++17	100 / 100	852 ms	8564 KiB

bulldozer

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define R(i,n,...) for(int i=__VA_ARGS__+0; i<n; i++)
using namespace std;

struct node {
	long 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 pii {
	int x, y;
	bool operator<(pii b) const { return x<b.x || x==b.x && y<b.y; }
	pii operator-(pii b) const { return {x-b.x, y-b.y}; }
	long operator^(pii b) const { return 1LL*x*b.y-1LL*y*b.x; }
};
struct iii {
	pii p; int w;
	bool operator<(const iii& b) const { return p<b.p; }
};

union evt {
	struct { unsigned short i, j; };
	unsigned int k;
};

int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	int N, K=0;
	cin>>N;
	iii A[N];
	int P[N];
	R(i, N) cin>>A[i].p.x>>A[i].p.y>>A[i].w;
	sort(A, A+N);
	iota(P, P+N, 0);

	evt E[N*(N-1)/2];
	R(i, N) R(j, i) E[K].i=i, E[K++].j=j;
	sort(E, E+K, [&](evt l, evt r) {
		auto x=A[l.i].p-A[l.j].p^A[r.i].p-A[r.j].p;
		return x<0 || !x && l.k<r.k;
	});

	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=N; i--;) {
		int w=A[i].w;
		T[i+2048]={w, w, w, w};
	}
	for(int i=2048; --i;)
		T[i]=T[i*2]+T[i*2+1];

	long mx=T[1].mx;
	for(int k=0; k<K; k++) {
		int i=E[k].i, j=E[k].j;
		swap(P[i], P[j]);
		upd(P[i], A[i].w);
		upd(P[j], A[j].w);
		if(k+1<K && !(A[i].p-A[j].p^A[E[k+1].i].p-A[E[k+1].j].p)) continue;
		mx=max(mx, T[1].mx);
	}
	cout<<mx;
}

Compilation message (stderr)

bulldozer.cpp: In member function 'bool pii::operator<(pii) const':
bulldozer.cpp:19:55: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   19 |  bool operator<(pii b) const { return x<b.x || x==b.x && y<b.y; }
      |                                                ~~~~~~~^~~~~~~~
bulldozer.cpp: In lambda function:
bulldozer.cpp:46:18: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   46 |   auto x=A[l.i].p-A[l.j].p^A[r.i].p-A[r.j].p;
      |          ~~~~~~~~^~~~~~~~~
bulldozer.cpp:47:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   47 |   return x<0 || !x && l.k<r.k;
      |                 ~~~^~~~~~~~~~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:68:23: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   68 |   if(k+1<K && !(A[i].p-A[j].p^A[E[k+1].i].p-A[E[k+1].j].p)) continue;
      |                 ~~~~~~^~~~~~~

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