제출 #1220768

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1220768		sleepntsheep	Bulldozer (JOI17_bulldozer)	C++20	55 / 100	641 ms	50080 KiB

bulldozer

#include <cstdio>
#include <vector>
#include <algorithm>
#include <tuple>
#include <numeric>

using namespace std;

#define N 2000
#define N_ 2048
#define L long long

struct Frac {
	L n, d;

	Frac(L x, L y) {
		if (x < 0 && y < 0)
			x = -x, y = -y;
		if (y < 0)
			x = -x, y = -y;
		L g = gcd(x, y);
		n = x / g, d = y / g;

		if (x == 0)
			n = 0, d = 1;
	}

	int isneg() const {
		return (n < 0) ^ (d < 0);
	}

	bool operator<(const Frac &o) const {
		if (isneg() && ! o.isneg()) return true;
		if (! isneg() && o.isneg()) return false;

		return n * o.d < d * o.n;
	}
};

struct Maxsegment {
	long long pre, suf, ans, sum;
	Maxsegment() : pre(0), suf(0), ans(0), sum(0) {}
	Maxsegment(long long x) : pre(max(0ll, x)), suf(max(0ll, x)), ans(max(0ll, x)), sum(x) {}
	friend Maxsegment operator+(Maxsegment a, Maxsegment b) {
		Maxsegment c;
		c.sum = a.sum + b.sum;
		c.pre = max(a.pre, a.sum + b.pre);
		c.suf = max(b.suf, b.sum + a.suf);
		c.ans = max({a.ans, b.ans, a.suf + b.pre});
		return c;
	}
} tt[N_ << 1];

long long answer;
int n, n_;

struct Gold {
	int x, y, v;
} g[N];


vector<tuple<Frac, int, int> > ev;

void pul(int i) {
	tt[i] = tt[i << 1] + tt[i << 1 | 1];
}
void fix(int i) {
	for (i += n_; i >>= 1; ) pul(i);
}

void sweep() {

	vector<int> p(n), q(n);
	iota(p.begin(), p.end(), 0);

	auto DB = [&]() {
		return ;
		printf(" Order now:  ");for(int i=0;i<n;++i)printf("%d ",g[p[i]].v);printf(" maxsegment + %lld\n",tt[1].ans);
	};

	sort(p.begin(), p.end(), [&](int i, int j) {
			return g[i].x < g[j].x;
			});

	for (int i = 0; i < n; ++i) tt[i + n_] = Maxsegment(g[p[i]].v);
	for (int i = n_ - 1; i >= 1; --i) pul(i);

	for (int i = 0; i < n; ++i) q[p[i]] = i;

	DB();

	sort(ev.begin(), ev.end());

	answer = tt[1].ans;

	for (auto [slope, ii, jj]: ev) {
		swap(tt[n_ + q[ii]], tt[n_ + q[jj]]);
		//printf(" [%d %d], Slope = %lld/%lld\n", g[ii].v, g[jj].v, slope.n,slope.d);
		fix(q[ii]), fix(q[jj]);
		swap(p[q[jj]], p[q[ii]]);
		swap(q[ii], q[jj]);

	DB();
		answer = max(answer, tt[1].ans);
	}
}

int main() {
	scanf("%d", &n);
	for (n_ = 1; n_ < n; n_ <<= 1);

	for (int i = 0; i < n; ++i) {
		scanf("%d%d%d", &g[i].x, &g[i].y, &g[i].v);
	}

	for (int i = 0; i < n; ++i) 
		for (int j = i + 1; j < n; ++j) {
			Frac m = Frac(g[i].y - g[j].y, g[i].x - g[j].x);
			ev.emplace_back(m, i, j);
		}

	sweep();

	printf("%lld\n", answer);

	return 0;
}

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

bulldozer.cpp: In function 'int main()':
bulldozer.cpp:109:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |         scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
bulldozer.cpp:113:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |                 scanf("%d%d%d", &g[i].x, &g[i].y, &g[i].v);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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