/*
*/
#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=2e18;
lld rez=-inf,pref[maxn],tree[maxn*4];
int n,curr_here[maxn],curr_pos[maxn];
struct srt_pii{
bool operator ()(pii a,pii b){
if(a.ff==-inf || b.ff==-inf)return a.ff<b.ff;
return a.ff*b.ss<b.ff*a.ss;
}
};
map<pii,vector<int>,srt_pii>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);
///printf("%lld %lld TACK1\n",a.x,a.y);
degree90(pom);
///printf("%lld %lld TACK2\n",b.x,b.y);
///printf("%lld %lld LINEJA2\n",pom.ff,pom.ss);
mapa[pom].pb(a.id);
mapa[pom].pb(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;
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]);
}
lld query(int x,int l,int r,int ll,int rr){
if(l>rr || r<ll)return 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));
}
void make_seg_tree(){
lld minn=0;
for(int i=1;i<=n;i++){
pref[i]=pref[i-1]+p[i].w;
update(1,1,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;
update(1,0,n,0,0);
for(i=0;i<rr;i++,rr--){
/// printf("%d %d AAFEWJKNGE\n",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]);
///printf("%lld %lld %d jeboteee\n",p[id1].x,p[id1].y,id1);
pref[id1]=pref[id1-1]+p[id1].w;
update(1,0,n,i,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++){
///printf("%lld %lld pts\n",p[i].x,p[i].y);
curr_here[i]=p[i].id;
curr_pos[p[i].id]=i;
}
extract_pairs();
make_seg_tree();
/*printf("%d AAA\n",rez);
for(int i=1;i<=n;i++)printf("%lld %lld | ",p[i].x,p[i].y);
printf("\n");
for(int i=1;i<=n;i++)printf("%lld ",pref[i]);
printf("\n");*/
for(map<pii,vector<int> >::iterator it=mapa.begin();it!=mapa.end();it++){
vector<int> vect=it->ss;
sort(vect.begin(),vect.end());
vect.resize(unique(vect.begin(),vect.end())-vect.begin());
int pos[vect.size()+10];
memset(pos,0,sizeof(pos));
///printf("%lld %lld KKK\n",it->ff.ff,it->ff.ss);
/*for(int i=0;i<vect.size();i++)
printf("%lld %lld point\n",p[curr_pos[vect[i]]].x,p[curr_pos[vect[i]]].y);*/
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==it->ff){
curr.pb(id2);
pos[j]=1;
}
}
process(curr);
}
/*for(int i=1;i<=n;i++)printf("%lld %lld | ",p[i].x,p[i].y);
printf("\n");
for(int i=1;i<=n;i++)printf("%lld ",pref[i]);
printf("\n");*/
for(int i=0;i<vect.size();i++){
int id=curr_pos[vect[i]];
///printf("%lld %lld ALAA JBTR\n",pref[id],query(1,0,n,0,id-1));
rez=max(rez,pref[id]-query(1,0,n,0,id-1));
}
}
printf("%lld\n",rez);
return 0;
}
Compilation message
bulldozer.cpp: In function 'void process(std::vector<int>&)':
bulldozer.cpp:148:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(;i<vect.size();i++){
~^~~~~~~~~~~~
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:190:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<vect.size();i++){
~^~~~~~~~~~~~
bulldozer.cpp:201:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=i+1;j<vect.size();j++){
~^~~~~~~~~~~~
bulldozer.cpp:224:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<vect.size();i++){
~^~~~~~~~~~~~
bulldozer.cpp:159:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
bulldozer.cpp:160: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 |
Correct |
13 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
504 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
1144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
1144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
1144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
504 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
