#include <bits/stdc++.h>
using namespace std;
#define int long long
struct point {
int x;
int y;
int w;
bool operator < (point p) {
if(x == p.x) return y > p.y;
return x < p.x;
}
};
struct frac {
int p;
int q;
frac() { }
frac(int _p, int _q) { p = _p; q = _q; }
};
struct node {
long long mx;
long long pref;
long long suff;
long long sum;
};
bool operator < (frac a, frac b) { return a.p * 1LL * b.q < b.p * 1LL * a.q; }
bool operator == (frac a, frac b) { return a.p * 1LL * b.q && a.q * 1LL * b.p; }
bool operator != (frac a, frac b) { return !(a == b); }
const int N = 2010;
int n;
point a[N];
vector<pair<frac, pair<int, int>>> slopes;
int order[N], pos[N];
node st[4 * N];
void update(int index, int l, int r, int x, int val) {
if(l > r || r < x || x < l) return;
if(l == r) {
st[index].mx = st[index].pref = st[index].suff = max(val, 0LL);
st[index].sum = val;
return;
}
int mid = (l + r) / 2;
if(x <= mid) update(2 * index, l, mid, x, val);
else update(2 * index + 1, mid + 1, r, x, val);
st[index].mx = max({st[2 * index].mx, st[2 * index + 1].mx, st[2 * index].suff + st[2 * index + 1].pref});
st[index].pref = max(st[2 * index].pref, st[2 * index].sum + st[2 * index + 1].pref);
st[index].suff = max(st[2 * index + 1].suff, st[2 * index + 1].sum + st[2 * index].suff);
st[index].sum = st[2 * index].sum + st[2 * index + 1].sum;
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i].x >> a[i].y >> a[i].w;
for(int i = 1; i <= n; i++) {
for(int j = i + 1; j <= n; j++) {
int sign = 1;
int dx = a[i].x - a[j].x, dy = a[i].y - a[j].y;
if(dx < 0) sign *= -1;
if(dy < 0) sign *= -1;
dx = abs(dx);
dy = abs(dy);
int g = __gcd(dx, dy);
dx /= g;
dy /= g;
if(dx != 0) dy *= sign;
if(a[i] < a[j]) slopes.push_back({frac(dy, dx), {i, j}});
else slopes.push_back({frac(dy, dx), {j, i}});
}
}
sort(slopes.begin(), slopes.end(), [&](pair<frac, pair<int, int>> x, pair<frac, pair<int, int>> y) {
if(x.first == y.first) {
pair<int, int> i = x.second, j = y.second;
if(i.first == j.first) return a[i.second] < a[j.second];
return a[i.first] < a[j.first];
}
return x.first < y.first;
});
for(int i = 1; i <= n; i++) order[i] = i;
sort(order + 1, order + n + 1, [&](int i, int j) {
return a[i] < a[j];
});
for(int i = 1; i <= n; i++) pos[order[i]] = i;
for(int i = 1; i <= n; i++) update(1, 1, n, i, a[order[i]].w);
long long ans = 0;
pair<frac, pair<int, int>> lst;
lst.first = frac(-1, -1);
for(pair<frac, pair<int, int>> slope : slopes) {
if(slope.first != lst.first) ans = max(ans, st[1].mx);
{
int i = slope.second.first, j = slope.second.second;
if(pos[i] < pos[j]) {
update(1, 1, n, pos[i], a[order[pos[j]]].w);
update(1, 1, n, pos[j], a[order[pos[i]]].w);
swap(order[pos[i]], order[pos[j]]);
swap(pos[i], pos[j]);
}
}
lst = slope;
}
ans = max(ans, st[1].mx);
cout << ans;
return 0;
}
Compilation message
bulldozer.cpp: In function 'bool operator==(frac, frac)':
bulldozer.cpp:32:54: warning: '*' in boolean context, suggest '&&' instead [-Wint-in-bool-context]
32 | bool operator == (frac a, frac b) { return a.p * 1LL * b.q && a.q * 1LL * b.p; }
| ~~~~~~~~~~^~~~~
bulldozer.cpp:32:73: warning: '*' in boolean context, suggest '&&' instead [-Wint-in-bool-context]
32 | bool operator == (frac a, frac b) { return a.p * 1LL * b.q && a.q * 1LL * b.p; }
| ~~~~~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
856 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
860 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
