#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <cstdio>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define F first
#define S second
#define PB push_back
#define INF 100000000000000000
struct li{
ll x,y;
bool operator<(const li&q)const{
if(y==0)return q.x*q.y>0;
if(q.y==0)return x*y<0;
return y*q.x<q.y*x;
}
};
struct qu{
ll x,y,k,a,b;
bool operator<(const qu&q)const{
if(y*q.x!=q.y*x){
if(y==0)return q.x*q.y>0;
if(q.y==0)return x*y<0;
return y*q.x<q.y*x;
}
return k<q.k;
}
};
struct po{
ll x,y,i;
bool operator<(const po&q)const{
if(x!=q.x)return x>q.x;
return y>q.y;
}
};
struct sgt{
ll x,ma,mi;
};
ll n,k,x[2005],y[2005],w[2005],pl[2005],ans,seg[1<<12],sma[1<<12],smi[1<<12];
vector<P>line[2005];
map<li,ll>o;
vector<qu>q;
vector<po>poi;
bool vi[2005][2005];
void add(int a,ll c){
a+=(1<<11)-1;
sma[a]+=c;
smi[a]+=c;
while(a>0){
a=(a-1)/2;
sma[a]=max(sma[a*2+1],sma[a*2+2]);
smi[a]=min(smi[a*2+1],smi[a*2+2]);
seg[a]=max(max(seg[a*2+1],seg[a*2+2]),sma[a*2+2]-smi[a*2+1]);
}
}
sgt que(int a,int b,int l,int r,int v){
if(r<a||b<l)return sgt{0,0,INF};
if(a<=l&&r<=b)return sgt{seg[v],sma[v],smi[v]};
sgt ls=que(a,b,l,(l+r-1)/2,v*2+1),rs=que(a,b,(l+r+1)/2,r,v*2+2);
return sgt{max(max(ls.x,rs.x),rs.ma-ls.mi),max(ls.ma,rs.ma),min(ls.mi,rs.mi)};
}
int main(void){
scanf("%lld",&n);
for(int i=0;i<n;i++)scanf("%lld%lld%lld",x+i,y+i,w+i);
for(int i=0;i<n;i++){
for(int j=0;j<k;j++)line[j].clear();
k=0;
o.clear();
for(int j=i+1;j<n;j++){
if(x[i]==x[j])continue;
li p={x[i]-x[j],y[i]-y[j]};
if(o.find(p)==o.end()){
line[k].PB(P(-x[i],i));
o[p]=k++;
}
line[o[p]].PB(P(-x[j],j));
}
for(int l=0;l<k;l++){
sort(line[l].begin(),line[l].end());
ll e=0;
for(int a=0;a<line[l].size();a++){
for(int b=a+1;b<line[l].size();b++){
int v=line[l][a].S,u=line[l][b].S;
if(vi[v][u]||vi[u][v])continue;
q.PB(qu{x[v]-x[u],y[v]-y[u],e,v,u});
e++;
vi[v][u]=true;
vi[u][v]=true;
}
}
}
}
for(int i=0;i<n;i++)poi.PB(po{x[i],y[i],i});
sort(poi.begin(),poi.end());
ll s=0;
for(int i=0;i<n;i++){
s+=w[poi[i].i];
pl[poi[i].i]=i+1;
add(i+1,s);
}
ans=max(ans,que(0,n,0,(1<<11)-1,0).x);
sort(q.begin(),q.end());
for(int i=0;i<q.size();i++){
vector<P>t;
t.PB(P(q[i].a,q[i].b));
while(i+1<q.size()&&q[i].y*q[i+1].x==q[i+1].y*q[i].x){
i++;
t.PB(P(q[i].a,q[i].b));
}
for(int j=0;j<t.size();j++){
ll a=pl[t[j].F],b=pl[t[j].S],wa=w[t[j].F],wb=w[t[j].S];
pl[t[j].F]=b;
pl[t[j].S]=a;
if(a>b){
swap(a,b);
swap(wa,wb);
}
add(a,-wa+wb);
}
ans=max(ans,que(0,n,0,(1<<11)-1,0).x);
}
printf("%lld\n",ans);
}
Compilation message
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:84:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int a=0;a<line[l].size();a++){
~^~~~~~~~~~~~~~~
bulldozer.cpp:85:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int b=a+1;b<line[l].size();b++){
~^~~~~~~~~~~~~~~
bulldozer.cpp:106:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<q.size();i++){
~^~~~~~~~~
bulldozer.cpp:109:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i+1<q.size()&&q[i].y*q[i+1].x==q[i+1].y*q[i].x){
~~~^~~~~~~~~
bulldozer.cpp:113:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<t.size();j++){
~^~~~~~~~~
bulldozer.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&n);
~~~~~^~~~~~~~~~~
bulldozer.cpp:67:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=0;i<n;i++)scanf("%lld%lld%lld",x+i,y+i,w+i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1120 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
1120 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1120 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
1120 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1120 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
1120 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
1084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
