#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Point {
ll x;
ll y;
ll value;
};
struct R {
int sgn;
ll up;
ll down;
int i;
int j;
};
R get(ll x, ll y) {
R sol;
ll g = __gcd(x, y);
x /= g;
y /= g;
sol.sgn = +1;
if (x < 0 && y < 0) {
x *= -1;
y *= -1;
}
if (x < 0 || y < 0) {
sol.sgn = -1;
}
sol.up = abs(x);
sol.down = abs(y);
return sol;
}
bool operator < (R a, R b) {
if (a.sgn != b.sgn) {
return a.sgn < b.sgn;
}
if (a.sgn == -1) {
swap(a, b);
}
return a.up * b.down < b.up * a.down;
}
bool initialCmp(Point a, Point b) {
if (a.y == b.y) {
return a.x < b.x;
}
return a.y < b.y;
}
const int N = 2000 + 7;
int n;
R panta[N][N];
Point points[N];
void sneakyHack() {
for (int i = 1; i <= n; i++) {
swap(points[i].x, points[i].y);
}
}
int ord[N];
int inv[N];
int main() {
bool isHome;
isHome = true;
isHome = false;
if (isHome) {
freopen ("input", "r", stdin);
} else {
ios::sync_with_stdio(0); cin.tie(0);
}
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> points[i].x >> points[i].y >> points[i].value;
}
ll best = 0;
for (int iteration = 1; iteration <= 2; iteration++) {
sneakyHack();
sort(points + 1, points + n + 1, initialCmp);
for (int i = 1; i <= n; i++) {
ord[i] = i;
inv[i] = i;
for (int j = i + 1; j <= n; j++) {
panta[i][j] = get(points[i].x - points[j].x, points[i].y - points[j].y);
panta[i][j].i = i;
panta[i][j].j = j;
}
}
vector<R> all;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
all.push_back(panta[i][j]);
}
}
stable_sort(all.begin(), all.end());
for (int i = 1; i <= n; i++) {
current = max(0LL, current + points[ord[i]].value);
best = max(best, current);
}
/// all[it] < all[it + 1]
int l = 0;
while (l < (int) all.size()) {
int r = l;
while (r + 1 < (int) all.size() && !(all[r] < all[r + 1])) {
r++;
}
for (int it = l; it <= r; it++) {
int i = all[it].i;
int j = all[it].j;
int pos_i = inv[i];
int pos_j = inv[j];
swap(ord[pos_i], ord[pos_j]);
inv[ord[pos_i]] = pos_i;
inv[ord[pos_j]] = pos_j;
}
long long current = 0;
for (int i = 1; i <= n; i++) {
current = max(0LL, current + points[ord[i]].value);
best = max(best, current);
}
l = r + 1;
}
}
cout << best << "\n";
return 0;
}
Compilation message
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:112:7: error: 'current' was not declared in this scope
112 | current = max(0LL, current + points[ord[i]].value);
| ^~~~~~~
bulldozer.cpp:79:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
79 | freopen ("input", "r", stdin);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
