#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll inf = 1e18;
const int OO = 0;
const int OOO = 1;
using namespace std;
struct point {
ll x, y, c, i;
point() {}
point(ll xx, ll yy, ll cc, int ii) {
x = xx;
y = yy;
c = cc;
i = ii;
}
bool operator < (const point &a) const {
if (y != a.y) return y < a.y;
return x < a.x;
}
};
struct block {
ll mx, L, R, S;
block(ll v = -inf) {
mx = L = R = S = v;
}
block operator * (const block &a) const {
block rtn;
rtn.S = S + a.S;
rtn.L = max(L, S + a.L);
rtn.R = max(R + a.S, a.R);
rtn.mx = max(max(mx, a.mx), R + a.L);
return rtn;
}
};
struct segtree {
int n;
vector<block> t;
segtree() {}
segtree(const vector<point> &a) {
n = max(2, (int)a.size());
while (n != (n & -n)) n += (n & -n);
t.resize(2 * n);
for (int i = 0; i < a.size(); i++)
t[i + n - 1] = block(a[i].c);
for (int i = n - 2; i >= 0; i--) fix(i);
}
void fix(int x) {
t[x] = t[x + x + 1] * t[x + x + 2];
}
void upd(int x, ll v) {
x += n - 1;
t[x] = block(v);
x = (x - 1) / 2;
while (x) {
fix(x);
x = (x - 1) / 2;
}
fix(0);
}
ll query() {
return t[0].mx;
}
};
struct eve {
ll x, y;
int u, v;
eve(ll xx = 0, ll yy = 0, int uu = 0, int vv = 0) {
x = xx;
y = yy;
if (y < 0) {
x = -x;
y = -y;
}
u = uu;
v = vv;
}
bool operator < (const eve &a) const {
return x * a.y - y * a.x > 0;
}
bool operator == (const eve &a) const {
return x * a.y == y * a.x;
}
};
int n;
vector<point> a;
vector<int> ind;
vector<eve> E;
segtree T;
ll ans = 0;
void apply(int i, int j) {
int u = a[i].i, v = a[j].i;
if (OO) {
cout << "swapping points\n";
cout << a[i].x << " " << a[i].y << '\n';
cout << a[j].x << " " << a[j].y << '\n';
cout << "which is indicies " << i << " " << j << '\n';
cout << "and in ind " << u << " " << v << '\n';
}
swap(a[i], a[j]);
swap(ind[u], ind[v]);
T.upd(i, a[i].c);
T.upd(j, a[j].c);
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
cin >> n;
a.resize(n);
E.reserve(n * (n - 1) / 2);
for (auto &i : a) cin >> i.x >> i.y >> i.c;
sort(a.begin(), a.end());
for (int i = 0; i < n; i++) a[i].i = i;
ind.resize(n);
for (int i = 0; i < n; i++) ind[i] = i;
for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++)
E.push_back(eve(a[j].x - a[i].x, a[j].y - a[i].y, i, j));
sort(E.begin(), E.end());
T = segtree(a);
if (OO) {
cout << "querying on\n";
for (const auto &i : a) cout << i.x << " " << i.y << '\n';
cout << "result = " << T.query() << '\n';
}
ans = max(ans, T.query());
int nxt = 0;
vector<pair<int, int>> those;
while (nxt < E.size()) {
those.clear();
do {
if (OO) cout << "adding event " << nxt << " " << E[nxt].x << " " << E[nxt].y << " " << E[nxt].u << " " << E[nxt].v << '\n';
those.emplace_back(min(ind[E[nxt].u], ind[E[nxt].v]), max(ind[E[nxt].u], ind[E[nxt].v]));
nxt++;
} while (nxt < E.size() && E[nxt - 1] == E[nxt]);
sort(those.begin(), those.end());
for (const auto &i : those) apply(i.first, i.second);
if (OO) {
cout << "querying on\n";
for (const auto &i : a) cout << i.x << " " << i.y << '\n';
cout << "result = " << T.query() << '\n';
}
ans = max(ans, T.query());
if (OO) {
cout << "now ind = \n";
for (const auto &i : ind) cout << i << " "; cout << '\n';
}
}
finish(ans);
}
Compilation message
bulldozer.cpp: In constructor 'segtree::segtree(const std::vector<point>&)':
bulldozer.cpp:50:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < a.size(); i++)
~~^~~~~~~~~~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:138:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (nxt < E.size()) {
~~~~^~~~~~~~~~
bulldozer.cpp:144:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
} while (nxt < E.size() && E[nxt - 1] == E[nxt]);
~~~~^~~~~~~~~~
bulldozer.cpp:156:4: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
for (const auto &i : ind) cout << i << " "; cout << '\n';
^~~
bulldozer.cpp:156:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
for (const auto &i : ind) cout << i << " "; cout << '\n';
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
