#include<bits/stdc++.h>
using namespace std;
vector<long long> x(5000);
vector<long long> y(5000);
vector<long long> w(5000);
bool comp(pair<long long,long long> a, pair<long long,long long> b) {
long long x1 = x[a.first]-x[a.second];
long long y1 = y[a.first]-y[a.second];
long long x2 = x[b.first]-x[b.second];
long long y2 = y[b.first]-y[b.second];
if(x1 < 0) {
x1*=-1;
y1*=-1;
}
if(x2 < 0) {
x2*=-1;
y2*=-1;
}
return x1*y2 < x2*y1;
}
bool check(pair<long long,long long> a, pair<long long,long long> b) {
long long x1 = x[a.first]-x[a.second];
long long y1 = y[a.first]-y[a.second];
long long x2 = x[b.first]-x[b.second];
long long y2 = y[b.first]-y[b.second];
return x1*y2 == x2*y1;
}
struct node {
long long pr = 0;
long long su = 0;
long long sb = 0;
long long ans = 0;
};
vector<node> seg(10000);
void upd(long long l, long long r, long long x, long long p, long long c) {
if(l == r) {
seg[x].sb = c;
seg[x].pr = max(c,0LL);
seg[x].su = max(c,0LL);
seg[x].ans = max(c,0LL);
return;
}
long long mid = (l+r)/2;
if(p <= mid) {
upd(l,mid,x*2,p,c);
}
else {
upd(mid+1,r,x*2+1,p,c);
}
seg[x].sb = seg[x*2].sb+seg[x*2+1].sb;
seg[x].pr = max(seg[x*2].pr,seg[x*2].sb+seg[x*2+1].pr);
seg[x].su = max(seg[x*2+1].su,seg[x*2+1].sb+seg[x*2].su);
seg[x].ans = max(seg[x*2].ans,seg[x*2+1].ans);
seg[x].ans = max(seg[x].ans,seg[x*2].su+seg[x*2+1].pr);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long n;
cin >> n;
for(long long i = 0; i < n; i++) {
cin >> x[i] >> y[i] >> w[i];
}
vector<pair<long long,long long>> idk(0);
for(long long i = 0; i < n; i++) {
for(long long j = i+1; j < n; j++) {
if(x[i] != x[j]) {
idk.push_back({i,j});
}
}
}
sort(idk.begin(),idk.end(),comp);
vector<pair<pair<long long,long long>,long long>> apple(0);
for(long long i = 0; i < n; i++) {
apple.push_back({{x[i],y[i]},i});
}
sort(apple.begin(),apple.end());
vector<long long> pos(n);
for(long long i = 0; i < n; i++) {
upd(0,n-1,1,i,w[apple[i].second]);
pos[apple[i].second] = i;
}
long long ans = 0;
ans = max(ans,seg[1].ans);
for(long long i = 0; i < idk.size(); i++) {
int r = i+1;
while(r < idk.size() && check(idk[i],idk[r])) {
r++;
}
for(int j = i; j < r; j++) {
long long a = idk[i].first,b = idk[i].second;
swap(apple[pos[a]],apple[pos[b]]);
upd(0,n-1,1,pos[a],w[b]);
upd(0,n-1,1,pos[b],w[a]);
swap(pos[a],pos[b]);
}
ans = max(ans,seg[1].ans);
i = r-1;
}
cout << ans;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |