//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 Frac {
ll p, q;
Frac() {}
Frac(ll p, ll q) : p(p), q(q) {}
bool operator<(const Frac& oth) const {
return p * oth.q < oth.p * q;
}
bool operator!=(const Frac& oth) const {
return make_pair(p, q) != make_pair(oth.p, oth.q);
}
};
struct Info {
ll p = 0ll, s = 0ll, m = 0ll, a = 0ll;
Info() = default;
Info(ll v) {
p = max(0ll, v);
s = max(0ll, v);
m = max(0ll, v);
a = v;
}
};
Info merge(Info& a, Info& b) {
Info ret;
ret.a = a.a + b.a;
ret.p = max(a.p, a.a + b.p);
ret.s = max(b.s, b.a + a.s);
ret.m = max({a.m, b.m, a.s + b.p, ret.p, ret.s});
return ret;
}
const int maxN = 1 << 11;
vector<Info> t(maxN * 4);
int sz;
void upd(int i, int v) {
i += sz;
t[i] = v;
i >>= 1;
while (i) {
t[i] = merge(t[i << 1], t[i << 1 | 1]);
i >>= 1;
}
}
signed main(int32_t argc, char *argv[]) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
sz = 1;
while (sz < n) sz <<= 1;
vector<array<ll, 3>> kek(n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < 3; ++j) {
cin >> kek[i][j];
}
}
ranges::sort(kek);
vector<tuple<Frac, int, int>> ev;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (kek[i][0] == kek[j][0]) continue;
ll p = kek[j][1] - kek[i][1];
ll q = kek[j][0] - kek[i][0];
ll g = __gcd(p, q);
p /= g, q /= g;
if (q < 0) p *= -1, q *= -1;
ev.emplace_back(Frac(p, q), i, j);
}
}
ranges::sort(ev);
vector<int> ord(n);
for (int i = 0; i < n; ++i) {
ord[i] = i;
upd(i, kek[i][2]);
}
ll ans = max(0ll, t[1].m);
int m = (int) ev.size();
for (int x = 0; x < m; ++x) {
auto [s, i, j] = ev[x];
swap(ord[i], ord[j]);
upd(ord[i], kek[i][2]);
upd(ord[j], kek[j][2]);
if (x == m - 1 || s != get<0>(ev[x + 1]))
ans = max(ans, t[1].m);
}
cout << ans;
}
/*
*/
Compilation message
bulldozer.cpp: In function 'int main(int32_t, char**)':
bulldozer.cpp:77:5: error: 'ranges' has not been declared
77 | ranges::sort(kek);
| ^~~~~~
bulldozer.cpp:90:5: error: 'ranges' has not been declared
90 | ranges::sort(ev);
| ^~~~~~
bulldozer.cpp:99:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
99 | auto [s, i, j] = ev[x];
| ^
