/*
*/
#include<bits/stdc++.h>
#define ff first
#define ss second
#define lld long long
#define pb push_back
using namespace std;
typedef pair<lld,lld> pii;
const int maxn=2e3+10;
lld inf=2e9+100;
lld rez=-inf*inf,pref[maxn],tree[maxn*4],mtree[maxn*4];
int n,curr_here[maxn],curr_pos[maxn];
bool srt_pii(pair<pii,int> a,pair<pii,int> b){
if(a.ff.ff==-inf || b.ff.ff==-inf)return a.ff.ff<b.ff.ff;
if(a.ff.ff==0 || b.ff.ff==0){
if(a.ff.ff==0 && b.ff.ff==0)return false;
if(b.ff.ff==0 && a.ff.ff>0)return false;
if(b.ff.ff==0 && a.ff.ff<0)return true;
if(a.ff.ff==0 && b.ff.ff<0)return false;
if(a.ff.ff==0 && b.ff.ff>0)return true;
}
return a.ff.ff*b.ff.ss<b.ff.ff*a.ff.ss;
}
vector<pair<pii,int> >mapa;
struct st{
lld x,y,w;
int id;
}p[maxn];
bool srt(st a,st b){
return (a.y<b.y)||(a.y==b.y && a.x<b.x);
}
void regulate(pii &x){
lld g=__gcd(x.ff,x.ss);
x.ff/=g;
x.ss/=g;
int cnt=0;
if(x.ff<0)cnt++;
if(x.ss<0)cnt++;
if(cnt==2){
x.ff*=-1;
x.ss*=-1;
}
else if(cnt==1){
if(x.ss<0){
x.ss*=-1;
x.ff*=-1;
}
}
}
pii get_line(st a,st b){
pii ret={0,0};
if(a.x==b.x)return {-inf,-inf};
if(a.y==b.y)return {0,0};
ret={a.y-b.y,a.x-b.x};
regulate(ret);
return ret;
}
void degree90(pii &x){
if(x.ff==-inf){
x={0,0};
return;
}
if(x.ff==0){
x={-inf,-inf};
return;
}
swap(x.ff,x.ss);
x.ff*=-1;
regulate(x);
}
void add_pair(st a,st b){
pii pom=get_line(a,b);
degree90(pom);
mapa.pb({pom,a.id});
mapa.pb({pom,b.id});
}
void extract_pairs(){
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
add_pair(p[i],p[j]);
}
void update(int x,int l,int r,int id,lld val){
if(l==r){
tree[x]=val;
mtree[x]=val;
return;
}
int mid=(l+r)/2;
if(id>mid)update(x*2+1,mid+1,r,id,val);
else update(x*2,l,mid,id,val);
tree[x]=min(tree[x*2],tree[x*2+1]);
mtree[x]=max(mtree[x*2],mtree[x*2+1]);
}
lld query(int x,int l,int r,int ll,int rr){
if(l>rr || r<ll)return inf*inf;
if(l>=ll && r<=rr)return tree[x];
int mid=(l+r)/2;
return min(query(x*2,l,mid,ll,rr),query(x*2+1,mid+1,r,ll,rr));
}
lld query2(int x,int l,int r,int ll,int rr){
if(l>rr || r<ll)return -inf*inf;
if(l>=ll && r<=rr)return mtree[x];
int mid=(l+r)/2;
return max(query2(x*2,l,mid,ll,rr),query2(x*2+1,mid+1,r,ll,rr));
}
void make_seg_tree(){
lld minn=0;
update(1,0,n,0,0);
for(int i=1;i<=n;i++){
pref[i]=pref[i-1]+p[i].w;
update(1,0,n,i,pref[i]);
minn=min(minn,pref[i]);
rez=max(rez,pref[i]-minn);
}
}
void process(vector<int> &vect){
sort(vect.begin(),vect.end());
int rr=vect.size()-1;
int i;
for(i=0;i<rr;i++,rr--){
int id1=vect[i];
int id2=vect[rr];
swap(curr_here[id1],curr_here[id2]);
swap(curr_pos[curr_here[id1]],curr_pos[curr_here[id2]]);
swap(p[id1],p[id2]);
pref[id1]=pref[id1-1]+p[id1].w;
update(1,0,n,id1,pref[id1]);
}
for(;i<vect.size();i++){
int id=vect[i];
pref[id]=pref[id-1]+p[id].w;
update(1,0,n,id,pref[id]);
}
}
int main(){
///freopen("test.txt","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lld %lld %lld",&p[i].x,&p[i].y,&p[i].w),p[i].id=i;
sort(p+1,p+n+1,srt);
for(int i=1;i<=n;i++){
curr_here[i]=p[i].id;
curr_pos[p[i].id]=i;
}
extract_pairs();
make_seg_tree();
sort(mapa.begin(),mapa.end(),srt_pii);
for(int pp=0;pp<mapa.size();pp++){
vector<int> vect;
vect.pb(mapa[pp].ss);
pii pah=mapa[pp].ff;
while(mapa[++pp].ss==mapa[pp].ss){
vect.pb(mapa[pp].ss);
}
pp--;
sort(vect.begin(),vect.end());
vect.resize(unique(vect.begin(),vect.end())-vect.begin());
int pos[vect.size()+10];
memset(pos,0,sizeof(pos));
for(int i=0;i<vect.size();i++){
if(pos[i])continue;
int id1=vect[i];
id1=curr_pos[id1];
pos[i]=1;
vector<int>curr;
curr.pb(id1);
for(int j=i+1;j<vect.size();j++){
if(pos[j])continue;
int id2=vect[j];
id2=curr_pos[id2];
pii pom=get_line(p[id1],p[id2]);
degree90(pom);
if(pom==pah){
curr.pb(id2);
pos[j]=1;
}
}
process(curr);
}
for(int i=0;i<vect.size();i++){
int id=curr_pos[vect[i]];
rez=max(rez,pref[id]-query(1,0,n,0,id-1));
rez=max(rez,-pref[id]+query2(1,0,n,id,n));
}
}
printf("%lld\n",rez);
return 0;
}
Compilation message
bulldozer.cpp: In function 'void process(std::vector<int>&)':
bulldozer.cpp:155:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(;i<vect.size();i++){
~^~~~~~~~~~~~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:179:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int pp=0;pp<mapa.size();pp++){
~~^~~~~~~~~~~~
bulldozer.cpp:183:20: warning: operation on 'pp' may be undefined [-Wsequence-point]
while(mapa[++pp].ss==mapa[pp].ss){
^~~~
bulldozer.cpp:194:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<vect.size();i++){
~^~~~~~~~~~~~
bulldozer.cpp:205:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=i+1;j<vect.size();j++){
~^~~~~~~~~~~~
bulldozer.cpp:223:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<vect.size();i++){
~^~~~~~~~~~~~
bulldozer.cpp:166:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
bulldozer.cpp:167:73: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=n;i++)scanf("%lld %lld %lld",&p[i].x,&p[i].y,&p[i].w),p[i].id=i;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
1396 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
1520 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
1520 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
1520 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
1396 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
