#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>
using namespace std;
typedef long long ll;
struct point {
int x, y;
point(int x, int y) : x(x), y(y) {}
point(int x) : x(x), y(x) {}
point() : x(0), y(0) {}
point operator -(const point &p) const {
return point(x - p.x, y - p.y);
}
ll operator *(const point &p) const {
return (ll)x * p.y - (ll)y * p.x;
}
int type() const {
return y > 0 || (y == 0 && x > 0);
}
bool operator ==(const point &p) const {
return x == p.x && y == p.y;
}
bool operator <(const point &b) const {
const point &a = *this;
if (a.type() != b.type()) {
return a.type() < b.type();
}
return a * b > 0;
}
};
const ll Inf = 1e18;
struct Node {
ll sum, best, max_pref, max_suf;
Node() {
sum = 0;
best = 0 ;
max_pref = max_suf = -Inf;
}
Node(ll x) {
sum = x;
best = max(x, 0LL);
max_pref = max(0LL, x);
max_suf = max(0LL, x);
}
Node operator +(const Node &other) const {
Node res;
res.best = max(best, other.best);
res.best = max(res.best, max_suf + other.max_pref);
res.sum = sum + other.sum;
res.max_pref = max(max_pref, sum + other.max_pref);
res.max_suf = max(other.max_suf, other.sum + max_suf);
return res;
}
};
const int N = 2507;
Node t[2 * N];
int n;
void modify(int id, ll val) {
t[n + id] = Node(val);
for (int v = (n + id) / 2; v >= 1; v /= 2) {
t[v] = t[2 * v] + t[2 * v + 1];
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
cin >> n;
map <pair <int, int>, ll> cost;
for (int i = 0; i < n; ++i) {
int x, y, w;
cin >> x >> y >> w;
cost[{x, y}] += w;
}
n = cost.size();
vector <point> a(n); vector <int> w(n);
{
int id = 0;
for (auto it = cost.begin(); it != cost.end(); ++it, ++id) {
a[id] = point((it->first).first, (it->first).second);
w[id] = it->second;
}
}
vector <pair <point, pair <int, int>>> dir;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i == j) continue;
dir.emplace_back(a[i] - a[j], make_pair(i, j));
}
}
sort(dir.begin(), dir.end());
vector <int> p(n);
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&] (int i, int j) {
if (a[i].y != a[j].y) return a[i].y < a[j].y;
return a[i].x > a[j].x;
});
vector <int> pos(n);
for (int i = 0; i < n; ++i) pos[p[i]] = i;
for (int i = 0; i < n; ++i) {
modify(pos[i], w[i]);
}
ll ans = t[1].best;
for (auto d : dir) {
int i = d.second.first, j = d.second.second;
modify(pos[i], w[j]);
modify(pos[j], w[i]);
swap(pos[i], pos[j]);
ans = max(ans, t[1].best);
}
cout << ans << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
