//I wrote this code 4 u <3
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
struct Point {
ll x, y, w;
Point() {}
Point(ll x, ll y, ll w) : x(x), y(y), w(w) {}
bool operator<(const Point& oth) const {
return x < oth.x || (x == oth.x && y > oth.y);
}
friend istream &operator>>(istream& in, Point& p) {
in >> p.x >> p.y >> p.w;
return in;
}
};
struct Frac {
ll p, q;
Frac() {}
Frac(ll _p, ll _q) : p(_p), q(_q) {}
bool operator<(const Frac& oth) const {
return 1ll * p * oth.q < 1ll * oth.p * q;
}
};
struct Info {
ll pref = 0, suf = 0, all = 0, mx = 0;
Info() {}
Info(ll v) : pref(max(0ll, v)), suf(max(0ll, v)), all(v), mx(max(0ll, v)) {}
};
Info operator+(const Info& a, const Info& b) {
Info ret;
ret.all = a.all + b.all;
ret.pref = max(a.pref, a.all + b.pref);
ret.suf = max(b.suf, a.suf + b.all);
ret.mx = max({ret.pref, ret.suf, a.mx, b.mx, a.suf + b.pref});
return ret;
}
template<class Info, class Merge = plus<Info>>
struct SegTree {
vector<Info> t;
const Merge merge;
int sz;
SegTree(int n) : merge(Merge()) {
sz = 1;
while (sz < n) sz <<= 1;
t.resize(sz << 1);
}
SegTree(vector<ll>& a) : merge(Merge()) {
sz = 1;
while (sz < (int) a.size()) sz <<= 1;
t.resize(sz << 1);
for (int i = 0; i < (int) a.size(); ++i) {
t[i + sz] = a[i];
}
for (int i = sz - 1; i; --i) {
pull(i);
}
}
void pull(int x) {
t[x] = merge(t[x << 1], t[x << 1 | 1]);
}
void upd(int i, Info v) {
i += sz;
t[i] = v;
i >>= 1;
while (i) {
pull(i);
i >>= 1;
}
}
Info get() { return t[1]; }
};
signed main(int32_t argc, char *argv[]) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<Point> kek(n);
for (int i = 0; i < n; ++i) {
cin >> kek[i];
}
vector<Frac> slope;
map<Frac, vector<pair<int, int>>> aboba;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
int dx = kek[i].x - kek[j].x, dy = kek[i].y - kek[j].y, sign = 1;
if (dx < 0) dx *= -1, sign *= -1;
if (dy < 0) dy *= -1, sign *= -1;
int g = __gcd(dx, dy);
dx /= g, dy /= g;
if (dx) dy *= sign;
if (kek[i] < kek[j]) aboba[{dy, dx}].emplace_back(i, j);
else aboba[{dy, dx}].emplace_back(j, i);
slope.emplace_back(dy, dx);
}
}
sort(slope.begin(), slope.end());
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
ranges::sort(ord, [&](int i, int j) {
return kek[i] < kek[j];
});
vector<int> pos(n);
SegTree<Info> st(n);
for (int i = 0; i < n; ++i) { pos[ord[i]] = i, st.upd(i, kek[ord[i]].w); }
ll ans = 0;
for (auto nw : slope) {
ans = max(ans, st.get().mx);
ranges::sort(aboba[nw], [&](const pair<int, int>& i, const pair<int, int>& j) {
if (i.first == j.first) return kek[i.second] < kek[j.second];
return kek[i.first] < kek[j.first];
});
for (auto [i, j] : aboba[nw]) {
if (pos[i] < pos[j]) {
st.upd(pos[i], kek[ord[pos[j]]].w);
st.upd(pos[j], kek[ord[pos[i]]].w);
swap(ord[pos[i]], ord[pos[j]]);
swap(pos[i], pos[j]);
}
}
}
cout << max(ans, st.get().mx);
}
/*
*/
Compilation message
bulldozer.cpp: In function 'int main(int32_t, char**)':
bulldozer.cpp:125:5: error: 'ranges' has not been declared
125 | ranges::sort(ord, [&](int i, int j) {
| ^~~~~~
bulldozer.cpp:134:9: error: 'ranges' has not been declared
134 | ranges::sort(aboba[nw], [&](const pair<int, int>& i, const pair<int, int>& j) {
| ^~~~~~
bulldozer.cpp:138:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
138 | for (auto [i, j] : aboba[nw]) {
| ^
