Submission #114805

#	Time	Username	Problem	Language	Result	Execution time	Memory
114805		imyujin	Bulldozer (JOI17_bulldozer)	C++14	0 / 100	4 ms	384 KiB

bulldozer

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

using namespace std;

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

typedef pair<int, int> pint;

const long long linf=1e9;

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

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);

	X[N]=linf+1;
	Y[N]=linf+1;
	W[N]=0;
	X[N+1]=linf+2;
	Y[N+1]=linf+1;
	W[N+1]=0;
	N+=2;
	
	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<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];
	for(int i=0; i<N; i++) ans=gmax(ans, W[i]);

	for(int i=0;;){
		sn=2;
		s[0]=degree[i].fi;
		s[1]=degree[i].se;
		for(i++; i<dn&&degdif(degree[i], degree[i-1])==0; i++){
			s[sn++]=pidx[degree[i].fi];
			s[sn++]=pidx[degree[i].se];
		}
		if(i==dn) break;

		//printf("[%d]\n", sn);

		nd=degree[i];
		sort(s, s+sn);
		sn=unique(s, s+sn)-s;
		for(int j=0; j<sn; j++) for(int k=j; k<sn-1; k++) if(distance(nd, point[s[k]])==distance(nd, point[s[k+1]])){
			int t=point[s[k]];
			point[s[k]]=point[s[k+1]];
			point[s[k+1]]=point[s[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(int j=0; j<N; j++) printf("%d ", point[j]);
		/*
		for(int j=0; j<N; j++) printf("%lld ", WW[j]);
		printf("\n%lld\n", seg[1][1]);
		printf("%lld\n", ans);
		*/
	}

	printf("%lld", ans);

	return 0;
}

Compilation message (stderr)

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:135:8: warning: unused variable 't' [-Wunused-variable]
    int t=point[s[k]];
        ^
bulldozer.cpp:97:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
bulldozer.cpp:98: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: 0 / 5
• Subtask 2: 0 / 20
• Subtask 3: 0 / 35
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20