#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;
point() {}
point(ll xx, ll yy, ll cc) {
x = xx;
y = yy;
c = cc;
}
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 = ind[i], v = ind[j];
if (OO) {
cout << "swapping points\n";
cout << a[u].x << " " << a[u].y << '\n';
cout << a[v].x << " " << a[v].y << '\n';
cout << "which is indicies " << u << " " << v << '\n';
}
swap(a[u], a[v]);
swap(ind[i], ind[j]);
T.upd(u, a[u].c);
T.upd(v, a[v].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());
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 {
those.emplace_back(E[nxt].u, E[nxt].v);
nxt++;
} while (nxt < E.size() && E[nxt - 1] == E[nxt]);
sort(those.begin(), those.end(), [](const pair<int, int> &aa, const pair<int, int> &bb) {
if (ind[aa.first] != ind[bb.first]) return ind[aa.first] < ind[bb.first];
return ind[aa.second] < ind[bb.second];
});
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());
}
finish(ans);
}
Compilation message
bulldozer.cpp: In constructor 'segtree::segtree(const std::vector<point>&)':
bulldozer.cpp:49: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:135:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (nxt < E.size()) {
~~~~^~~~~~~~~~
bulldozer.cpp:140:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
} while (nxt < E.size() && E[nxt - 1] == E[nxt]);
~~~~^~~~~~~~~~
| # |
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 |
- |
