Submission #114989

#	Time	Username	Problem	Language	Result	Execution time	Memory
114989		imyujin	Bulldozer (JOI17_bulldozer)	C++14	80 / 100	1387 ms	16476 KiB

bulldozer

#include<stdio.h>
#include<algorithm>

using namespace std;

#define MAXN 2005
#define fi first
#define se second

typedef pair<int, int> pint;

long long X[MAXN], Y[MAXN], W[MAXN];
pint degree[MAXN*MAXN];
int dn;
int point[MAXN], pidx[MAXN];
pint nd;
long long seg[4*MAXN][4];
int s[MAXN], sn;

long long distance(pint d, int p){
	long long dx=X[d.fi]-X[d.se], dy=Y[d.fi]-Y[d.se];
	if(dx<0){
		dx*=-1;
		dy*=-1;
	}
	else if(dx==0) dy=1;

	return dy*X[p]-dx*Y[p];
}

long long degdif(pint a, pint b){
	long long dx1=X[a.fi]-X[a.se], dy1=Y[a.fi]-Y[a.se], dx2=X[b.fi]-X[b.se], dy2=Y[b.fi]-Y[b.se];
	if(dx1<0){
		dx1*=-1;
		dy1*=-1;
	}
	else if(dx1==0) dy1=1;
	if(dx2<0){
		dx2*=-1;
		dy2*=-1;
	}
	else if(dx2==0) dy2=1;
	return dy1*dx2-dx1*dy2;
}

bool cmpdeg(pint a, pint b){
	return degdif(a, b)>0;
}

bool cmppoint(int a, int b){
	return X[a]!=X[b] ? X[a]<X[b] : Y[a]<Y[b];
}

long long gmax(long long a, long long b){
	return a>b?a:b;
}

void mkseg(int idx, int l, int r){
	if(l==r){
		seg[idx][0]=W[point[l]];
		seg[idx][1]=seg[idx][2]=seg[idx][3]=gmax(W[point[l]], 0);
	}
	else{
		int m=(l+r)/2;
		mkseg(idx*2, l, m);
		mkseg(idx*2+1, m+1, r);
		seg[idx][0]=seg[idx*2][0]+seg[idx*2+1][0];
		seg[idx][1]=gmax(seg[idx*2][3]+seg[idx*2+1][2], gmax(seg[idx*2][1], seg[idx*2+1][1]));
		seg[idx][2]=gmax(seg[idx*2][2], seg[idx*2][0]+seg[idx*2+1][2]);
		seg[idx][3]=gmax(seg[idx*2+1][3], seg[idx*2][3]+seg[idx*2+1][0]);
	}
}

void updseg(int idx, int l, int r, int c){
	if(l==r){
		seg[idx][0]=W[point[l]];
		seg[idx][1]=seg[idx][2]=seg[idx][3]=gmax(W[point[l]], 0);
	}
	else{
		int m=(l+r)/2;
		if(c<=m) updseg(idx*2, l, m, c);
		else updseg(idx*2+1, m+1, r, c);
		seg[idx][0]=seg[idx*2][0]+seg[idx*2+1][0];
		seg[idx][1]=gmax(seg[idx*2][3]+seg[idx*2+1][2], gmax(seg[idx*2][1], seg[idx*2+1][1]));
		seg[idx][2]=gmax(seg[idx*2][2], seg[idx*2][0]+seg[idx*2+1][2]);
		seg[idx][3]=gmax(seg[idx*2+1][3], seg[idx*2][3]+seg[idx*2+1][0]);
	}
}

int main(){
	int N;
	long long ans;
	
	scanf("%d", &N);
	for(int i=0; i<N; i++) scanf("%lld%lld%lld", X+i, Y+i, W+i);
	
	for(int i=0; i<N; i++) for(int j=i+1; j<N; j++) degree[dn++]=make_pair(i, j);
	sort(degree, degree+dn, cmpdeg);
	//for(int i=0; i<dn; i++) printf("%d %d\n", degree[i].fi, degree[i].se);

	for(int i=0; i<N; i++) point[i]=i;
	nd=degree[0];
	sort(point, point+N, cmppoint);
	for(int i=0; i<N; i++) pidx[point[i]]=i;
	mkseg(1, 0, N-1);
	ans=seg[1][1];
	
	//printf("%d\n", N);

	for(int i=0; i<dn;){
		/*
		for(int j=0; j<N; j++) printf("%d ", point[j]);
		printf("\n");
		*/
		sn=0;
		for(int j=i; j<dn&&degdif(degree[j], degree[i])==0; j++){
			s[sn++]=pidx[degree[j].fi];
			s[sn++]=pidx[degree[j].se];
		}
		/*
		for(int j=0; j<sn; j++) printf("*%d", point[s[j]]);
		printf("\n");
		*/

		nd=degree[i];
		sort(s, s+sn);
		sn=unique(s, s+sn)-s;
		for(int j=0; j<sn;){
			int k;
			for(k=0; j+k<sn&&distance(nd, point[s[j+k]])==distance(nd, point[s[j]]); k++);
			for(int l=0; l<k/2; l++){
				int t=point[s[j+l]];
				point[s[j+l]]=point[s[j+k-1-l]];
				point[s[j+k-1-l]]=t;
			}
			j+=k;
		}
		for(int j=0; j<sn; j++){
			pidx[point[s[j]]]=s[j];
			updseg(1, 0, N-1, s[j]);
		}

		ans=gmax(ans, seg[1][1]);
		for(i++; i<dn&&degdif(degree[i], degree[i-1])==0; i++);
	}

	printf("%lld", ans);
	return 0;
}

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:94:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
bulldozer.cpp:95:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<N; i++) scanf("%lld%lld%lld", X+i, Y+i, W+i);
                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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