제출 #51788

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
51788		ainta	Bulldozer (JOI17_bulldozer)	C++17	75 / 100	568 ms	31872 KiB

bulldozer

#include<cstdio>
#include<algorithm>
#define SZ 2048
using namespace std;
struct point2 {
	int x, y, i, j;
	bool operator<(const point2 &p)const {
		return (long long)y*p.x  < (long long)p.y*x;
	}
}P[2010000];
struct point {
	int x, y, c;
	bool operator<(const point &p)const {
		return x != p.x ? x < p.x : y < p.y;
	}
}w[2010];
long long res;
int n,cnt, Loc[2010];
struct Tree {
	long long L[SZ + SZ], R[SZ + SZ], S[SZ + SZ], M[SZ + SZ];
	void Put(int a, int b) {
		a += SZ;
		S[a] = b;
		L[a] = R[a] = M[a] = max(0, b);
		while (a != 1) {
			a >>= 1;
			S[a] = S[a + a] + S[a + a + 1];
			L[a] = max(L[a + a], S[a + a] + L[a + a + 1]);
			R[a] = max(R[a + a + 1], S[a + a + 1] + R[a + a]);
			M[a] = max(max(M[a + a], M[a + a + 1]), R[a + a] + L[a + a + 1]);
		}
	}
}T;
int main() {
	int i, j;
	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		scanf("%d%d%d", &w[i].x, &w[i].y, &w[i].c);
	}
	sort(w + 1, w + n + 1);
	for (i = 1; i < n; i++) {
		for (j = i + 1; j <= n; j++) {
			int dx = w[j].x - w[i].x, dy = w[j].y - w[i].y;
			if (dx < 0 || (dx == 0 && dy < 0))dx = -dx, dy = -dy;
			P[cnt++] = { dx,dy,i,j };
		}
	}
	for (i = 1; i <= n; i++) {
		Loc[i] = i;
		T.Put(i, w[i].c);
	}
	sort(P, P + cnt);
	res = T.M[1];
	for (i = 0; i < cnt; i++) {
		for (j = i; j < cnt; j++) {
			if ((long long)P[i].x*P[j].y != (long long)P[i].y*P[j].x)break;
			int a = P[j].i, b = P[j].j;
			swap(Loc[a], Loc[b]);
			T.Put(Loc[a], w[a].c);
			T.Put(Loc[b], w[b].c);
		}
		res = max(res, T.M[1]);
		i = j - 1;
	}
	printf("%lld\n", res);
}

컴파일 시 표준 에러 (stderr) 메시지

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
bulldozer.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &w[i].x, &w[i].y, &w[i].c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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