oj.uz

Submission #114414

# Submission time Handle Problem Language Result Execution time Memory
114414 2019-06-01T09:03:44 Z 임유진(#2862) Bulldozer (JOI17_bulldozer) C++14
0 / 100
 5 ms 432 KB 
#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 WW[MAXN];
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 cmpdis(int a, int b){
	return distance(nd, a)<distance(nd, 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]=WW[l];
		seg[idx][1]=seg[idx][2]=seg[idx][3]=gmax(WW[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]=WW[l];
		seg[idx][1]=seg[idx][2]=seg[idx][3]=gmax(WW[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, cmpdis);
	for(int i=0; i<N; i++) pidx[point[i]]=i;
	for(int i=0; i<N; i++) WW[i]=W[point[i]];
	for(int i=N-1; i>0; i--) if(distance(nd, point[i])==distance(nd, point[i-1])){
		WW[i-1]+=WW[i];
		WW[i]=0;
	}
	//for(int i=0; i<N; i++) printf("%lld ", WW[i]);
	//printf("\n");
	mkseg(1, 0, N-1);
	ans=seg[1][1];

	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++]=degree[i].fi;
			s[sn++]=degree[i].se;
		}
		if(i==dn) break;

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

		nd=degree[i];
		sort(s, s+sn, cmpdis);
		sn=unique(s, s+sn)-s;
		for(int j=0; j<sn; j++){
			pidxt[j]=pidx[s[j]];
		}
		sort(pidxt, pidxt+sn);
		for(int j=0; j<sn; j++){
			point[pidxt[j]]=s[j];
			pidx[s[j]]=pidxt[j];
			WW[pidxt[j]]=W[s[j]];
		}
		for(int j=0; j<sn; j++) updseg(1, 0, N-1, pidxt[j]);

		//for(int j=0; j<N; j++) printf("%lld ", WW[j]);
		//printf("\n%lld\n", seg[1][1]);

		sn=0;
		for(int j=i; j<dn&&degdif(degree[i], degree[j])==0; j++){
			s[sn++]=pidx[degree[j].fi];
			s[sn++]=pidx[degree[j].se];
		}
		sort(s, s+sn);
		sn=unique(s, s+sn)-s;
		//for(int j=0; j<sn; j++) printf("%d ", s[j]);
		//printf("*\n");
		for(int j=sn-1; j>0; j--) if(s[j-1]==s[j]-1){
			WW[s[j]-1]+=WW[s[j]];
			WW[s[j]]=0;
		}
		for(int j=0; j<sn; 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

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
bulldozer.cpp:99: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.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 428 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 432 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 356 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 4 ms 384 KB Output is correct
22 Correct 4 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 4 ms 384 KB Output is correct
25 Incorrect 4 ms 384 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 428 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 432 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 356 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 4 ms 384 KB Output is correct
22 Correct 4 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 4 ms 384 KB Output is correct
25 Incorrect 4 ms 384 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 428 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 432 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 356 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 4 ms 384 KB Output is correct
22 Correct 4 ms 384 KB Output is correct
23 Correct 5 ms 384 KB Output is correct
24 Correct 4 ms 384 KB Output is correct
25 Incorrect 4 ms 384 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -