Submission #309259

#	Time	Username	Problem	Language	Result	Execution time	Memory
309259		cgiosy	Bulldozer (JOI17_bulldozer)	C++17	0 / 100	2 ms	512 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; }
};

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;
	pii A[N];
	int W[N], P[N];
	iota(P, P+N, 0);
	R(i, N) cin>>A[i].x>>A[i].y>>W[i];
	sort(A, A+N);

	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]-A[l.j]^A[r.i]-A[r.j];
		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=0; i<N; i++) {
		int x=W[i];
		T[i+2048]={x, x, x, x};
	}
	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], W[i]);
		upd(P[j], W[j]);
		if(k+1<K && !(A[i]-A[j]^A[E[k+1].i]-A[E[k+1].j])) 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:42:16: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   42 |   auto x=A[l.i]-A[l.j]^A[r.i]-A[r.j];
      |          ~~~~~~^~~~~~~
bulldozer.cpp:43:20: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   43 |   return x<0 || !x && l.k<r.k;
      |                 ~~~^~~~~~~~~~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:64:21: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   64 |   if(k+1<K && !(A[i]-A[j]^A[E[k+1].i]-A[E[k+1].j])) continue;
      |                 ~~~~^~~~~

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