#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include <bits/stdc++.h> using namespace std; #define itachi ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define int long long #define fi first #define se second const int MAXN = 2005; struct Point { int x, y, w; }; struct Node { int sum, pref, suff, ans; Node(int v = 0) { sum = v; pref = suff = ans = max(0LL, v); } }; Node mergeNode(const Node &L, const Node &R) { Node res; res.sum = L.sum + R.sum; res.pref = max(L.pref, L.sum + R.pref); res.suff = max(R.suff, R.sum + L.suff); res.ans = max({L.ans, R.ans, L.suff + R.pref}); return res; } struct Event { int u, v; int dx, dy; bool operator < (const Event &o) const { int val = dy * o.dx - o.dy * dx; if (val) return val < 0; if (u != o.u) return u < o.u; return v < o.v; } bool operator == (const Event &o) const { return dy * o.dx == o.dy * dx; } }; int n; Point a[MAXN]; int pos[MAXN]; Node st[4 * MAXN]; void update(int id, int l, int r, int p, int val) { if (l == r) { st[id] = Node(val); return; } int m = (l + r) >> 1; if (p <= m) update(id << 1, l, m, p, val); else update(id << 1 | 1, m + 1, r, p, val); st[id] = mergeNode(st[id << 1], st[id << 1 | 1]); } signed main() { itachi cin >> n; for (int i = 0; i < n; i++) cin >> a[i].x >> a[i].y >> a[i].w; sort(a, a + n, [](const Point &A, const Point &B) { if (A.x != B.x) return A.x < B.x; return A.y < B.y; }); for (int i = 0; i < n; i++) { pos[i] = i; update(1, 0, n - 1, i, a[i].w); } vector<Event> ev; ev.reserve(n * n / 2); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { int dx = a[j].x - a[i].x; int dy = a[j].y - a[i].y; if (dx < 0 || (dx == 0 && dy < 0)) { dx = -dx; dy = -dy; } ev.push_back({i, j, dx, dy}); } } sort(ev.begin(), ev.end()); int ans = st[1].ans; for (int i = 0; i < (int)ev.size(); ) { int j = i; while (j < (int)ev.size() && ev[i] == ev[j]) { int u = ev[j].u; int v = ev[j].v; int pu = pos[u]; int pv = pos[v]; swap(pos[u], pos[v]); swap(a[pu], a[pv]); update(1, 0, n - 1, pu, a[pu].w); update(1, 0, n - 1, pv, a[pv].w); j++; } ans = max(ans, st[1].ans); i = j; } cout << ans; return 0; }

In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from bulldozer.cpp:4:
/usr/include/c++/13/bits/allocator.h: In destructor 'constexpr std::_Vector_base<Event, std::allocator<Event> >::_Vector_impl::~_Vector_impl()':
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to 'always_inline' 'constexpr std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = Event]': target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~