Submission #224607

#	Time	Username	Problem	Language	Result	Execution time	Memory
224607		dolphingarlic	Bulldozer (JOI17_bulldozer)	C++14	100 / 100	1090 ms	47616 KiB

bulldozer

#include <bits/stdc++.h>
#define FOR(i,x,y) for (int i=x; i<y; i++)
typedef long long ll;
using namespace std;

struct X{
	ll l,r,t,b;
	X operator+(X B){
		return{max(l,t+B.l),max(B.r,r+B.t),t+B.t,max(max(b,B.b),r+B.l)};
	}
}T[8001];

struct Y{
	ll x,y,v;
	bool operator<(Y B){
		if (x==B.x) return y<B.y;
		return x<B.x;
	}
}P[2001];

struct Z{
	ll x,y;
	int u,v;
	bool operator<(Z B){
		if (y*B.x==B.y*x) return tie(u,v)<tie(B.u,B.v);
		return y*B.x<B.y*x;
	}
}S[2000001];

int n,C[2001];

void B(int N=1,int l=1,int r=n){
	if (l==r){
		ll v=max(P[l].v,0ll);
		T[N]={v,v,P[l].v,v};
	}else{
		int M=(l+r) / 2;
		B(N*2,l,M);
		B(N*2+1,M+1,r);
		T[N]=T[N*2]+T[N*2+1];
	}
}

void U(int o,ll a,int N=1,int l=1,int r=n){
	if (l==r) T[N]={max(a,0ll),max(a,0ll),a,max(a,0ll)};
	else{
		int M=(l+r) / 2;
		if (o > M) U(o,a,N*2+1,M+1,r);
		else U(o,a,N*2,l,M);
		T[N]=T[N*2]+T[N*2+1];
	}
}

int main(){
	cin >> n;
	FOR(i,1,n+1){
		cin >> P[i].x >> P[i].y >> P[i].v;
		C[i]=i;
	}
	sort(P+1,P+n+1);
	int G=0;
	FOR(i,1,n+1) FOR(j,i+1,n+1)
		S[G++]={P[j].x - P[i].x,P[j].y - P[i].y,i,j};
	sort(S,S+G);

	B();
	ll H=T[1].b;
	FOR(i,0,G){
		U(C[S[i].u],P[S[i].v].v);
		U(C[S[i].v],P[S[i].u].v);
		swap(C[S[i].u],C[S[i].v]);

		if (i==G - 1) H=max(H,T[1].b);
		else if (S[i].y*S[i+1].x != S[i+1].y*S[i].x) H=max(H,T[1].b);
	}
	cout << H;
	return 0;
}

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