#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
const int INF = 1e9;
struct Point {
int x, y, w;
} a[N];
struct Node {
long long s, sl, sr, mx;
Node () { s = sl = sr = 0, mx = -INF; }
};
struct Go {
double w;
int x, y;
Go (double w, int x, int y) :
w(w), x(x), y(y) {}
};
int n, pos[N];
long long res;
Node it[4 * N];
vector<Go> go;
Node Merge(Node x, Node y) {
Node z;
z.s = x.s + y.s;
z.sl = max(x.sl, x.s + y.sl);
z.sr = max(x.s + y.sr, y.sr);
z.mx = max(max(x.mx, y.mx), x.sr + y.sl);
return z;
}
void build(int i, int l, int r) {
if (l == r) {
it[i].s = it[i].sl = it[i].sr = it[i].mx = a[l].w; return;
}
int mid = (l + r) >> 1;
build(i << 1, l, mid), build(i << 1 | 1, mid + 1, r);
it[i] = Merge(it[i << 1], it[i << 1 | 1]);
}
void upd(int i, int l, int r, int p, int v) {
if (l == r) {
it[i].s = it[i].sl = it[i].sr = it[i].mx = v; return;
}
int mid = (l + r) >> 1;
if (p <= mid) upd(i << 1, l, mid, p, v);
else upd(i << 1 | 1, mid + 1, r, p, v);
it[i] = Merge(it[i << 1], it[i << 1 | 1]);
}
int main() {
ios::sync_with_stdio(false);
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i].x >> a[i].y >> a[i].w;
}
sort(a, a + n, [&](Point x, Point y) {
return x.y < y.y;
});
// for (int i = 0; i < n; ++i) {
// cout << a[i].x << ' ' << a[i].y << ' ' << a[i].w << '\n';
// }
for (int i = 0; i < n; ++i) pos[i] = i;
build(1, 0, n - 1);
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
double tmp = atan2(a[j].y - a[i].y, a[j].x - a[i].x);
if (tmp == acos(-1)) tmp = 0;
go.push_back(Go(tmp, i, j));
}
}
sort(go.begin(), go.end(), [&](Go x, Go y) {
return x.w < y.w;
});
for (int i = 0; i < go.size(); ++i) {
vector<Go> _go;
_go.push_back(go[i]);
while (i + 1 < go.size() && go[i + 1].w == go[i].w) {
i++, _go.push_back(go[i]);
}
// cout << ".\n";
for (auto j : _go) {
swap(pos[j.x], pos[j.y]);
// cout << j.x << ' ' << j.y << ' ' << j.w << '\n';
upd(1, 0, n - 1, pos[j.x], a[j.x].w);
upd(1, 0, n - 1, pos[j.y], a[j.y].w);
}
res = max(res, it[1].mx);
}
cout << res << '\n';
}
Compilation message
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:82:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < go.size(); ++i) {
~~^~~~~~~~~~~
bulldozer.cpp:85:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (i + 1 < go.size() && go[i + 1].w == go[i].w) {
~~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
768 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
