#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P,P> PP;
typedef vector<ll> vi;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<PP> vpp;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define pb emplace_back
#define fi first
#define se second
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
const ll inf=1001001001001001001;
ll gcd(ll a,ll b){
if(b==0)return a;
return gcd(b,a%b);
}
class segtree{
vi seg;ll N=1;
public:
segtree(vi v){
while(N<v.size())N*=2;
seg=vi(N*2-1);
rep(i,v.size())seg[i+N-1]=v[i];
for(ll i=N-2;i>=0;i--)seg[i]=max(seg[i*2+1],seg[i*2+2]);
}
void add(ll i,ll x){
i+=N-1;
seg[i]+=x;
while(i>0){
i=(i-1)/2;
seg[i]=max(seg[i*2+1],seg[i*2+2]);
}
}
ll get(ll a,ll b,ll k=0,ll l=0,ll r=-1){
if(r==-1)r=N;
if(a<=l&&r<=b)return seg[k];
if(r<=a||b<=l)return 0;
ll c1=get(a,b,k*2+1,l,(l+r)/2);
ll c2=get(a,b,k*2+2,(l+r)/2,r);
return max(c1,c2);
}
void debug(ll n){
vi res;
rep(i,n)res.pb(seg[i+N-1]);
outv(res);
}
};
int main(){
ll n;cin>>n;
vvi tmp(n,vi(3));
rep(i,n)rep(j,3)cin>>tmp[i][j];
sort(all(tmp));
vp v(n);vi val(n);rep(i,n)v[i]=P(tmp[i][0],tmp[i][1]);rep(i,n)val[i]=tmp[i][2];
vpp srt;
rep(i,n)rep(j,i){
ll a=v[i].fi-v[j].fi,b=v[i].se-v[j].se;
if(a!=0){
ll g=gcd(abs(a),abs(b));
a/=g;b/=g;
srt.pb(P(a,b),P(j,i));
}
else srt.pb(P(1,inf),P(j,i));
}
auto cmp=[&](PP a,PP b){
if(a.fi!=b.fi)return a.fi.se*b.fi.fi<a.fi.fi*b.fi.se;
return a.se<b.se;
};
sort(all(srt),cmp);
vi ruil=val,ruir=val;
rep(i,n-1)ruil[i+1]+=ruil[i];
for(int i=n-1;i>0;i--)ruir[i-1]+=ruir[i];
segtree segl(ruil),segr(ruir);
ll ans=0;
ll l=0;
vi num(n),mun(n);
rep(i,n)num[i]=mun[i]=i;
while(l<srt.size()){
ll r=l;
while(r+1<srt.size()&&srt[l].fi==srt[r+1].fi)r++;
REP(i,l,r+1){
ll a=srt[i].se.fi,b=srt[i].se.se;
ll ok=-1,ng=n;
while(ng-ok>1){
ll md=(ok+ng)/2;
ll c=num[md];
ll x1=v[a].fi-v[b].fi,y1=v[a].se-v[b].se;
ll x2=v[c].fi-v[b].fi,y2=v[c].se-v[b].se;
if(x1*y2>x2*y1)ok=md;
else ng=md;
}
chmax(ans,segr.get(0,ok+1)-segr.get(mun[b]+1,mun[b]+2));
ok=n;ng=-1;
while(ok-ng>1){
ll md=(ok+ng)/2;
ll c=num[md];
ll x1=v[a].fi-v[b].fi,y1=v[a].se-v[b].se;
ll x2=v[c].fi-v[b].fi,y2=v[c].se-v[b].se;
if(x1*y2<x2*y1)ok=md;
else ng=md;
}
chmax(ans,segl.get(ok,n)-segl.get(mun[a]-1,mun[a]));
chmax(ans,val[a]+val[b]);
}
REP(i,l,r+1){
ll a=srt[i].se.fi,b=srt[i].se.se;
ll A=mun[a],B=mun[b];
if(A>B){
swap(a,b);swap(A,B);
}
assert(B-A==1);
swap(num[A],num[B]);
swap(mun[a],mun[b]);
segl.add(A,val[b]-val[a]);
segr.add(B,val[a]-val[b]);
}
assert(l==r);
// outp(srt[l].se);
// out(ans);
// segl.debug(n);
// segr.debug(n);
l=r+1;
}
// outvp(v);outv(val);
out(ans);
}
Compilation message
bulldozer.cpp: In constructor 'segtree::segtree(vi)':
bulldozer.cpp:34:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | while(N<v.size())N*=2;
| ~^~~~~~~~~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:90:12: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | while(l<srt.size()){
| ~^~~~~~~~~~~
bulldozer.cpp:92:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
92 | while(r+1<srt.size()&&srt[l].fi==srt[r+1].fi)r++;
| ~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
1000 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
1000 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
