#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;
}
};
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/=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]);
}
}
ll que(int a,int b){
ll res=0,ma=-INF,mi=INF;
a+=(1<<11)+1;
b+=(1<<11)+1;
for (;a<b; a>>=1,b>>=1) {
if(a&1){
res=max(res,seg[a]);
mi=min(mi,smi[a]);
res=max(res,sma[a]-mi);
a++;
}
if(b&1){
b--;
res=max(res,seg[b]);
ma=max(ma,sma[b]);
res=max(res,ma-smi[b]);
}
res=max(res,ma-mi);
}
return res;
}
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));
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));
}
printf("%lld\n",ans);
}
Compilation message
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:96:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int a=0;a<line[l].size();a++){
~^~~~~~~~~~~~~~~
bulldozer.cpp:97:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int b=a+1;b<line[l].size();b++){
~^~~~~~~~~~~~~~~
bulldozer.cpp:118:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<q.size();i++){
~^~~~~~~~~
bulldozer.cpp:121: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:125:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<t.size();j++){
~^~~~~~~~~
bulldozer.cpp:78:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&n);
~~~~~^~~~~~~~~~~
bulldozer.cpp:79: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 |
3 ms |
1084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
1120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
1120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
1120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
