#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define dbg(x) cerr << #x << ": " << x << endl;
struct Point {
ll x;
ll y;
ll cost;
Point(ll _x = 0, ll _y = 0, ll _cost = 0) : x(_x), y(_y), cost(_cost) {}
};
struct Vec {
ll x;
ll y;
Vec(ll _x = 0, ll _y = 0) : x(_x), y(_y) {}
Vec(const Point& p1, const Point& p2) {
x = p2.x - p1.x;
y = p2.y - p1.y;
}
ll operator*(const Vec& other) const {
return x * other.x + y * other.y;
}
ll operator^(const Vec& other) const {
return x * other.y - other.x * y;
}
};
struct Line {
ll a;
ll b;
ll c;
Line(ll _a = 0, ll _b = 0, ll _c = 0) : a(_a), b(_b), c(_c) {}
Line(const Point& p1, const Point& p2) {
a = p2.y - p1.y;
b = p1.x - p2.x;
c = p2.x * p1.y - p1.x * p2.y;
}
Line(const Line& line, const Point& p) {
a = line.a;
b = line.b;
c = -p.x * a - p.y * b;
}
Line get_orthogonal() const {
return {-b, a, c};
}
ll get(const Point& p) {
return a * p.x + b * p.y + c;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
ll ans = 0;
vector<Point> points(n);
for (auto& [x, y, cost] : points) {
cin >> x >> y >> cost;
ans = max(ans, cost);
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
Line line(points[i], points[j]);
// sorting by distance to the line
vector<vector<Point>> a(2);
ans = max(ans, points[i].cost + points[j].cost);
for (const auto& p : points) {
if (line.get(p) > 0) {
a[0].push_back(p);
} else if (line.get(p) < 0) {
a[1].push_back(p);
}
}
for (int t = 0; t <= 1; ++t) {
sort(a[t].begin(), a[t].end(), [&](const auto& p1, const auto& p2) {
return abs(line.get(p1)) < abs(line.get(p2));
});
ll pref = points[i].cost + points[j].cost;
ll min_pref = min(0LL, pref);
for (const auto& p : a[t]) {
pref += p.cost;
min_pref = min(min_pref, pref);
ans = max(ans, pref - min_pref);
}
}
}
}
cout << ans << '\n';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
51 ms |
312 KB |
Output is correct |
2 |
Correct |
51 ms |
312 KB |
Output is correct |
3 |
Correct |
51 ms |
316 KB |
Output is correct |
4 |
Correct |
59 ms |
312 KB |
Output is correct |
5 |
Correct |
56 ms |
212 KB |
Output is correct |
6 |
Correct |
53 ms |
212 KB |
Output is correct |
7 |
Correct |
50 ms |
312 KB |
Output is correct |
8 |
Correct |
53 ms |
320 KB |
Output is correct |
9 |
Correct |
52 ms |
212 KB |
Output is correct |
10 |
Correct |
56 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
51 ms |
312 KB |
Output is correct |
2 |
Correct |
51 ms |
312 KB |
Output is correct |
3 |
Correct |
51 ms |
316 KB |
Output is correct |
4 |
Correct |
59 ms |
312 KB |
Output is correct |
5 |
Correct |
56 ms |
212 KB |
Output is correct |
6 |
Correct |
53 ms |
212 KB |
Output is correct |
7 |
Correct |
50 ms |
312 KB |
Output is correct |
8 |
Correct |
53 ms |
320 KB |
Output is correct |
9 |
Correct |
52 ms |
212 KB |
Output is correct |
10 |
Correct |
56 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
51 ms |
312 KB |
Output is correct |
2 |
Correct |
51 ms |
312 KB |
Output is correct |
3 |
Correct |
51 ms |
316 KB |
Output is correct |
4 |
Correct |
59 ms |
312 KB |
Output is correct |
5 |
Correct |
56 ms |
212 KB |
Output is correct |
6 |
Correct |
53 ms |
212 KB |
Output is correct |
7 |
Correct |
50 ms |
312 KB |
Output is correct |
8 |
Correct |
53 ms |
320 KB |
Output is correct |
9 |
Correct |
52 ms |
212 KB |
Output is correct |
10 |
Correct |
56 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
2 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |