제출 #102675

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
102675		Minnakhmetov	Bulldozer (JOI17_bulldozer)	C++14	25 / 100	2016 ms	236040 KiB

bulldozer

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <cstring>
#include <unordered_map>
#include <unordered_set>

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")


using namespace std;

#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
#pragma warning(disable : 4996)

ll gcd(ll a, ll b) {
	return a ? gcd(b % a, a) : b;
}

struct P {
	ll x, y, w;
	bool operator < (const P &oth) const {
		return x * oth.y - y * oth.x > 0;
	}
	bool operator == (const P &oth) const {
		return x * oth.y - y * oth.x == 0;
	}
	ll operator * (const P &oth) const {
		return x * oth.y - y * oth.x;
	}
};

struct Line {
	ll a, b, c;
	int i, j;
	Line() {}
	Line(P &p, P &q, int i, int j) : i(i), j(j) {
		a = p.y - q.y;
		b = q.x - p.x;
		c = -p.y * (q.x - p.x) + (q.y - p.y) * p.x;

		ll g = gcd(gcd(a, b), c);

		a /= g;
		b /= g;
		c /= g;

		if (b < 0 || b == 0 && a < 0) {
			a = -a;
			b = -b;
			c = -c;
		}
	}
	bool operator < (const Line &oth) const {
		ll prod = a * oth.b - b * oth.a;
		return prod == 0 ? c < oth.c : prod > 0;
	}
	bool operator == (const Line &oth) const {
		return a == oth.a && b == oth.b && c == oth.c;
	}
};

const ll INF = 1e18;
const int N = 2005;
P a[N];
ll t[N * 4], mnp[N * 4], mxp[N * 4], pref[N], up[N * 4];
int pos[N];
int n;

Line b[N * N];
vector<int> lt[N * N];
vector<pair<int, int>> ev;
P d[N * N];

void mrg(int v) {
	t[v] = max(t[v * 2], t[v * 2 + 1]);
	t[v] = max(t[v], mxp[v * 2 + 1] - mnp[v * 2]);
	mxp[v] = max(mxp[v * 2], mxp[v * 2 + 1]);
	mnp[v] = min(mnp[v * 2], mnp[v * 2 + 1]);
}

void build(int v = 1, int L = 0, int R = n) {
	if (L == R) {
		t[v] = 0;
		mxp[v] = mnp[v] = pref[L];
	}
	else {
		int m = (L + R) >> 1;
		build(v * 2, L, m);
		build(v * 2 + 1, m + 1, R);
		mrg(v);
	}
}

void push(int v, int L, int R) {
	if (up[v]) {
		if (L != R) {
			up[v * 2] += up[v];
			up[v * 2 + 1] += up[v];
		}
		mnp[v] += up[v];
		mxp[v] += up[v];
		up[v] = 0;
	}
}

void upd(int l, int r, int x, int v = 1, int L = 0, int R = n) {
	push(v, L, R);
	if (l > r)
		return;
	if (l == L && r == R) {
		up[v] += x;
		push(v, L, R);
	}
	else {
		int m = (L + R) >> 1;
		upd(l, min(m, r), x, v * 2, L, m);
		upd(max(m + 1, l), r, x, v * 2 + 1, m + 1, R);
		mrg(v);
	}
}

signed main() {
#ifdef HOME
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;

	for (int i = 1; i <= n; i++) {
		int x, y, w;
		cin >> x >> y >> w;
		a[i] = { x, y, w };
	}

	sort(a + 1, a + n + 1, [](P &a, P &b) {
		return a.x == b.x ? a.y > b.y : a.x < b.x;
	});

	int ct = 0;
	for (int i = 1; i <= n; i++) {
		pos[i] = i;
		pref[i] = pref[i - 1] + a[i].w;
		for (int j = i + 1; j <= n; j++) {
			b[ct++] = Line(a[i], a[j], i, j);
		}
	}

	sort(b, b + ct);

	int ctd = 0, ctl = 0;
	for (int i = 0, j = 0; i < ct; i++) {
		bool fl = i == 0;
		if (i > 0) {
			if (!(b[i - 1] == b[i])) {
				ctl++;
				fl = true;
			}
			if (b[i - 1].a * b[i].b - b[i - 1].b * b[i].a != 0) {
				j++;
				fl = true;
			}
		}
		if (fl)
			ev.push_back({ j, ctl });
		lt[ctl].push_back(b[i].i);
		lt[ctl].push_back(b[i].j);
	}
	ctl++;

	for (int i = 0; i < ctl; i++) {
		sort(all(lt[i]));
		lt[i].erase(unique(all(lt[i])), lt[i].end());
	}

	build();

	ll ans = t[1];

	for (int i = 0; i < ev.size(); i++) {
		int lb = N, rb = -1;
		for (int x : lt[ev[i].second]) {
			lb = min(lb, pos[x]);
			rb = max(rb, pos[x]);
		}
		for (int x : lt[ev[i].second]) {
			int np = rb - pos[x] + lb;

			if (np < pos[x])
				upd(np, pos[x] - 1, a[x].w);
			else
				upd(pos[x], np - 1, -a[x].w);

			pos[x] = np;
		}

		if (i == ev.size() - 1 || ev[i + 1].first != ev[i].first)
			ans = max(ans, t[1]);
	}

	cout << ans;

	return 0;
}

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

bulldozer.cpp:45:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable : 4996)
 
bulldozer.cpp: In constructor 'Line::Line(P&, P&, int, int)':
bulldozer.cpp:79:23: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   if (b < 0 || b == 0 && a < 0) {
                ~~~~~~~^~~~~~~~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:214:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ev.size(); i++) {
                  ~~^~~~~~~~~~~
bulldozer.cpp:231:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i == ev.size() - 1 || ev[i + 1].first != ev[i].first)
       ~~^~~~~~~~~~~~~~~~
bulldozer.cpp:185:6: warning: unused variable 'ctd' [-Wunused-variable]
  int ctd = 0, ctl = 0;
      ^~~

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