#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<P,int> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int n,cur;
int x[4005],y[4005],w[4005];
vector<pair<P,vector<int> > >vi;
P1 za[4005];
bool cmp(const int&p,const int&q){
//cur-p-q
P a = za[cur].fi,b = za[p].fi,c = za[q].fi;
ll val = 1LL*(b.fi-a.fi)*(c.sc-a.sc)-1LL*(b.sc-a.sc)*(c.fi-a.fi);
if(val) return val > 0LL;
else return 1LL*(b.fi-a.fi)*(b.fi-a.fi)+1LL*(b.sc-a.sc)*(b.sc-a.sc) < 1LL*(c.fi-a.fi)*(c.fi-a.fi)+1LL*(c.sc-a.sc)*(c.sc-a.sc);
}
bool eq(P a,P b,P c){
return 1LL*(b.fi-a.fi)*(c.sc-a.sc)-1LL*(b.sc-a.sc)*(c.fi-a.fi) == 0;
}
bool cmp2(const pair<P,vector<int> >&p,const pair<P,vector<int> >&q){
P a = mp(0,0),b = p.fi,c = q.fi;
ll val = 1LL*(b.fi-a.fi)*(c.sc-a.sc)-1LL*(b.sc-a.sc)*(c.fi-a.fi);
return val > 0ll;
}
bool cmp3(const P1 &a,const P1&b){
if(a.fi.sc != b.fi.sc){
return a.fi.sc < b.fi.sc;
}
else{
return a.fi.fi > b.fi.fi;
}
}
int rev[4005],now[4005]; //rev[i] .. where is node i on segtree
struct segtree{
ll seg[(1<<13)],L[(1<<13)],R[(1<<13)],sum[(1<<13)];
void update(int k,int val){
k += (1<<12)-1;
seg[k] = max(0ll,1LL*val);
L[k] = max(0ll,1LL*val);
R[k] = max(0ll,1LL*val);
sum[k] = 1LL*val;
while(k>0){
k = (k-1)/2;
sum[k] = sum[k*2+1]+sum[k*2+2];
L[k] = max(L[k*2+1],sum[k*2+1]+L[k*2+2]);
R[k] = max(R[k*2+2],sum[k*2+2]+R[k*2+1]);
seg[k] = max(max(seg[k*2+1],seg[k*2+2]),R[k*2+1]+L[k*2+2]);
}
}
ll query(){ return seg[0]; }
int get(int k){ return sum[k+(1<<12)-1]; }
}seg;
bool used[4005][4005];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d%d",&x[i],&y[i],&w[i]);
za[i] = mp(mp(x[i],y[i]),i);
}
sort(za+1,za+n+1,cmp3);
for(int i=1;i<=n;i++){
vector<int>vec;
for(int j=i+1;j<=n;j++){
int X = za[j].fi.fi-za[i].fi.fi,Y = za[j].fi.sc-za[i].fi.sc;
{
vec.push_back(j);
}
}
cur = i;
sort(vec.begin(),vec.end(),cmp);
vector<int>L; L.clear(); L.pb(za[i].sc);
for(int j=0;j<vec.size();j++){
L.pb(za[vec[j]].sc);
if(j+1 != vec.size() && eq(za[i].fi,za[vec[j]].fi,za[vec[j+1]].fi)){
continue;
}
if(used[L[0]][L[1]]) {L.clear(); L.pb(za[i].sc); continue;}
P p = mp(za[vec[j]].fi.fi-za[i].fi.fi,za[vec[j]].fi.sc-za[i].fi.sc);
vi.pb(mp(p,L));
for(int k=0;k<L.size();k++) for(int l=k+1;l<L.size();l++) used[L[k]][L[l]] = used[L[l]][L[k]] = 1;
L.clear(); L.pb(za[i].sc);
}
}
sort(vi.begin(),vi.end(),cmp2);
//0+eps kara start
// sort(za+1,za+n+1,cmp3);
for(int i=1;i<=n;i++){
seg.update(i,1LL*w[za[i].sc]);
rev[za[i].sc] = i; now[i] = za[i].sc;
}
ll ans = seg.query();
for(int i=0;i<vi.size();i++){
vector<int>&hoge = vi[i].sc;
int e = -1;
for(int j=0;j<hoge.size();j++){
int hs = hoge.size(); int f = rev[hoge[hs-1-j]];
assert(e==-1 || abs(e-f) == 1); e = f;
seg.update(rev[hoge[j]],w[now[f]]);
}
for(int j=0;;j++){
int hs = hoge.size();
int f = rev[hoge[j]],g = rev[hoge[hs-1-j]];
if(0 >= hs-1-j*2) break;
swap(now[f],now[g]);
swap(rev[hoge[j]],rev[hoge[hs-1-j]]);
}
if(i+1 != vi.size() && eq(mp(0,0),vi[i].fi,vi[i+1].fi)) continue;
ans = max(ans,seg.query());
}
printf("%lld\n",ans);
}
Compilation message
bulldozer.c:1:10: fatal error: bits/stdc++.h: No such file or directory
#include <bits/stdc++.h>
^~~~~~~~~~~~~~~
compilation terminated.
