#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 a,b;
bool operator<(const li&q)const{
return b*q.a<q.b*a;
}
};
struct qu{
ll x,y,a,b;
bool operator<(const qu&q)const{
if(x==0||q.x==0)return x*y>q.x*q.y;
if(x*y>0==q.x*q.y>0)return y*q.x<x*q.y;
return x*y>q.x*q.y;
}
bool operator>(const qu&q)const{
if(x==0||q.x==0)return x*y<q.x*q.y;
if(x*y>0==q.x*q.y>0)return y*q.x>x*q.y;
return x*y<q.x*q.y;
}
};
struct poi{
ll x,y,i;
bool operator<(const poi&q)const{
if(y!=q.y)return y<q.y;
return x>q.x;
}
bool operator>(const poi&q)const{
if(y!=q.y)return y>q.y;
return x<q.x;
}
};
ll n,x[2005],y[2005],w[2005],k,pl[2005],ans,la[1<<12];
P seg[1<<12];
vector<P>lin[2005];
map<li,int>o;
vector<qu>q;
vector<poi>po;
void lazy(int l,int r,int v){
if(la[v]==0)return;
seg[v].F+=la[v];
seg[v].S+=la[v];
if(l!=r){
la[v*2+1]+=la[v];
la[v*2+2]+=la[v];
}
la[v]=0;
}
void add(int a,int b,int l,int r,int v,ll c){
if(r<a||b<l){
lazy(l,r,v);
return;
}
if(a<=l&&r<=b){
la[v]+=c;
lazy(l,r,v);
return;
}
lazy(l,r,v);
add(a,b,l,(l+r-1)/2,v*2+1,c);
add(a,b,(l+r+1)/2,r,v*2+2,c);
seg[v].F=max(seg[v*2+1].F,seg[v*2+2].F);
seg[v].S=min(seg[v*2+1].S,seg[v*2+2].S);
}
ll ma(int a,int b,int l,int r,int v){
lazy(l,r,v);
if(r<a||b<l)return 0;
if(a<=l&&r<=b)return seg[v].F;
return max(ma(a,b,l,(l+r-1)/2,v*2+1),ma(a,b,(l+r+1)/2,r,v*2+2));
}
ll mi(int a,int b,int l,int r,int v){
lazy(l,r,v);
if(r<a||b<l)return INF;
if(a<=l&&r<=b)return seg[v].S;
return min(mi(a,b,l,(l+r-1)/2,v*2+1),mi(a,b,(l+r+1)/2,r,v*2+2));
}
int main(void){
scanf("%lld",&n);
for(int i=0;i<n;i++){
scanf("%lld%lld%lld",x+i,y+i,w+i);
po.PB(poi{x[i],y[i],i});
}
for(int i=0;i<n;i++){
for(int j=0;j<k;j++)lin[j].clear();
k=0;
o.clear();
for(int j=i+1;j<n;j++){
if(y[i]==y[j])continue;
li z={x[i]-x[j],y[i]-y[j]};
if(o.find(z)==o.end()){
lin[k].PB(P(y[i],i));
o[z]=k++;
}
lin[o[z]].PB(P(y[j],j));
}
for(int j=0;j<k;j++){
sort(lin[j].begin(),lin[j].end());
for(int r=0;r<lin[j].size()-1-r;r++){
int v=lin[j][r].S,u=lin[j][lin[j].size()-1-r].S;
q.PB(qu{x[v]-x[u],y[v]-y[u],v,u});
}
}
}
sort(po.begin(),po.end());
ll m=0,s=0;
for(int i=0;i<n;i++){
pl[po[i].i]=i+1;
s+=w[po[i].i];
add(i+1,i+1,0,(1<<11)-1,0,s);
ans=max(ans,s-m);
m=min(m,s);
}
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,b-1,0,(1<<11)-1,0,-wa+wb);
}
for(int j=0;j<t.size();j++){
ll a=pl[t[j].F],b=pl[t[j].S];
ans=max(ans,mi(a,a,0,(1<<11)-1,0)-mi(0,a,0,(1<<11)-1,0));
ans=max(ans,ma(a,n,0,(1<<11)-1,0)-mi(a-1,a-1,0,(1<<11)-1,0));
ans=max(ans,mi(b,b,0,(1<<11)-1,0)-mi(0,b,0,(1<<11)-1,0));
ans=max(ans,ma(b,n,0,(1<<11)-1,0)-mi(b-1,b-1,0,(1<<11)-1,0));
}
}
printf("%lld\n",ans);
}
Compilation message
bulldozer.cpp: In member function 'bool qu::operator<(const qu&) const':
bulldozer.cpp:23:13: warning: suggest parentheses around comparison in operand of '==' [-Wparentheses]
if(x*y>0==q.x*q.y>0)return y*q.x<x*q.y;
~~~^~
bulldozer.cpp: In member function 'bool qu::operator>(const qu&) const':
bulldozer.cpp:28:13: warning: suggest parentheses around comparison in operand of '==' [-Wparentheses]
if(x*y>0==q.x*q.y>0)return y*q.x>x*q.y;
~~~^~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:108:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int r=0;r<lin[j].size()-1-r;r++){
~^~~~~~~~~~~~~~~~~~
bulldozer.cpp:124:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<q.size();i++){
~^~~~~~~~~
bulldozer.cpp:127: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:127:44: warning: suggest parentheses around comparison in operand of '==' [-Wparentheses]
while(i+1<q.size()&&q[i].y*q[i+1].x==q[i+1].y==q[i].x){
bulldozer.cpp:131:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<t.size();j++){
~^~~~~~~~~
bulldozer.cpp:141:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<t.size();j++){
~^~~~~~~~~
bulldozer.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&n);
~~~~~^~~~~~~~~~~
bulldozer.cpp:90:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld",x+i,y+i,w+i);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
356 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
764 KB |
Output is correct |
2 |
Incorrect |
12 ms |
764 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
764 KB |
Output is correct |
2 |
Incorrect |
12 ms |
764 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
764 KB |
Output is correct |
2 |
Incorrect |
12 ms |
764 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
0 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
356 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
12 ms |
764 KB |
Output is correct |
17 |
Incorrect |
12 ms |
764 KB |
Output isn't correct |
18 |
Halted |
0 ms |
0 KB |
- |