#include <bits/stdc++.h>
#define F first
#define S second
#define all(a) begin(a), end(a)
#define pb push_back
#define eb emplace_back
using namespace std;
using ll = long long;
using cll = complex<long long>;
using pii = pair<int, int>;
int n;
vector<pair<cll, ll>> v;
ll inline cross(cll a, cll b) {
return (conj(a) * b).imag();
}
ll inline ccw(cll a, cll b, cll c) {
return cross(b - a, c - b);
}
bool inline sign(cll a) {
return a.imag() > 0 || (a.imag() == 0 && a.real() > 0);
}
vector<pair<cll, pair<int, int>>> events;
struct Item {
ll mxPref = 0, mxSuf = 0, mxSuma = 0, suma = 0;
};
struct SegTree {
int static const N = (1 << 11);
array<Item, 2 * N> val;
Item merg(Item a, Item b) {
Item ret;
ret.mxPref = max(a.mxPref, a.suma + b.mxPref);
ret.mxSuf = max(b.mxSuf, b.suma + a.mxSuf);
ret.suma = a.suma + b.suma;
ret.mxSuma = max({a.mxSuma, b.mxSuma, a.mxSuf + b.mxPref});
return ret;
}
void upd(int p, ll elem, int ver, int lx, int rx) {
if (rx - lx == 1) {
val[ver].mxPref = val[ver].mxSuf = val[ver].mxSuma = val[ver].suma = elem;
return;
}
int mid = (lx + rx) / 2;
if (p < mid) upd(p, elem, ver * 2 + 1, lx, mid);
else upd(p, elem, ver * 2 + 2, mid, rx);
val[ver] = merg(val[ver * 2 + 1], val[ver * 2 + 2]);
}
void upd(int p, ll elem) { upd(p, elem, 0, 0, N); }
ll query() { return val[0].mxSuma; }
};
int pos[2010];
void solve() {
cin >> n;
v.resize(n);
for (auto &[p, val] : v) {
ll a, b;
cin >> a >> b >> val;
p.real(a);
p.imag(b);
}
sort(all(v), [](auto const &a, auto const &b) {
return a.F.real() < b.F.real() || (a.F.real() == b.F.real() && a.F.imag() > b.F.imag());
});
SegTree st;
for (int i = 0; i < n; ++i) {
st.upd(i, v[i].S);
}
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
events.eb((v[j].F - v[i].F) * cll(0, 1), pii{i, j});
events.eb((v[j].F - v[i].F) * cll(0, -1), pii{j, i});
}
}
sort(all(events), [&](auto const &a, auto const &b) {
if (sign(a.F) != sign(b.F)) return sign(a.F) > sign(b.F);
ll c = ccw(cll(0, 0), a.F, b.F);
if (c == 0) return a.S < b.S;
return c > 0;
});
ll res = st.query();
iota(pos, pos + n + 10, 0);
for (int i = 0; i < size(events); ++i) {
auto p = events[i].S;
st.upd(pos[p.F], v[p.S].S);
st.upd(pos[p.S], v[p.F].S);
swap(pos[p.F], pos[p.S]);
if (i + 1 < size(events) && ccw(cll(0, 0), events[i].F, events[].F) == 0) continue;
res = max(res, st.query());
}
cout << res << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
Compilation message
bulldozer.cpp: In function 'void solve()':
bulldozer.cpp:96:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::complex<long long int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for (int i = 0; i < size(events); ++i) {
| ~~^~~~~~~~~~~~~~
bulldozer.cpp:101:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::complex<long long int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
101 | if (i + 1 < size(events) && ccw(cll(0, 0), events[i].F, events[].F) == 0) continue;
| ~~~~~~^~~~~~~~~~~~~~
bulldozer.cpp:101:72: error: expected primary-expression before ']' token
101 | if (i + 1 < size(events) && ccw(cll(0, 0), events[i].F, events[].F) == 0) continue;
| ^
