Submission #265424

#	Time	Username	Problem	Language	Result	Execution time	Memory
265424		islingr	Bulldozer (JOI17_bulldozer)	C++17	25 / 100	2092 ms	152692 KiB

bulldozer

#include <bits/stdc++.h>
using namespace std;

const int N = 1 << 17;
using ll = int64_t;
const ll inf = 1e18;
struct S {
	ll pref, suff, ans, sum;
	S(ll x = 0) : sum{x} { ans = pref = suff = x > 0 ? x : 0; }
	S(const S &l, const S &r) : ans{max(l.ans, r.ans)} {
		pref = max(l.pref, l.sum + r.pref);
		suff = max(l.suff + r.sum, r.suff);
		ans = max(ans, l.suff + r.pref);
		sum = l.sum + r.sum;
	}
} t[N << 1];

int sz = 1;
void update(int p, ll x) { for (t[p += sz] = x; p >>= 1; ) t[p] = {t[p << 1], t[p << 1|1]}; }

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define all(x...) begin(x), end(x)

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

using point = complex<ll>;
ll cross(const point &a, const point &b) { return imag(conj(a) * b); }
struct cmp {
	bool operator()(const point &a, const point &b) const { return cross(a, b) > 0; }
};

map<point, vector<pair<int, int>>, cmp> m;
int w[N], ord[N], pos[N];
point p[N];
vector<int> g[N], line;
bool vis[N];

void dfs(int u) {
	vis[u] = 1; line.push_back(u);
	for (int v : g[u]) if (!vis[v]) dfs(v);
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n; cin >> n; while (sz < n) sz <<= 1;
	rep(i, 0, n) { int x, y; cin >> x >> y >> w[i]; p[i] = {x, y}; ord[i] = i; }
	sort(ord, ord + n, [&](int a, int b) {
		return pair(imag(p[a]), -real(p[a])) < pair(imag(p[b]), -real(p[b]));
	});
	rep(i, 0, n) pos[ord[i]] = i;
	rep(i, 0, n) update(pos[i], w[i]);

	rep(i, 0, n) {
		rep(j, i + 1, n) {
			point z = p[i] - p[j];
			ll g = gcd(real(z), imag(z));
			z = {real(z) / g, imag(z) / g};
			if (imag(z) <= 0) z = -z;
			m[z].emplace_back(i, j);
			m[z].emplace_back(j, i);
		}
	}

	ll ans = t[1].ans;
	for (auto &[_, d] : m) {
		for (auto &[u, v] : d) g[u].push_back(v);
		for (auto &[_, v] : d) {
			if (vis[v]) continue;
			line.clear(); dfs(v);
			sort(all(line), [&](int x, int y) { return real(p[x]) < real(p[y]);});
			int s = line.size();
			for (int i = 0; i < s - i - 1; ++i)
				swap(pos[line[i]], pos[line[s - i - 1]]);
			for (int i : line) update(pos[i], w[i]);
		}

		for (auto &[_, v] : d) g[v].clear(), vis[v] = 0;
		ans = max(ans, t[1].ans);
	}

	cout << ans << '\n';
}

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