#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,s[2005];
P seg[1<<12];
vector<P>lin[2005];
map<li,int>o;
vector<qu>q;
vector<poi>po;
void add(int a,ll c){
a+=(1<<11)-1;
seg[a].F+=c;
seg[a].S+=c;
while(a>0){
a=(a-1)/2;
seg[a].F=max(seg[a*2+1].F,seg[a*2+2].F);
seg[a].S=min(seg[a*2+1].S,seg[a*2+2].S);
}
}
ll ma(int a,int b,int l,int r,int 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){
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});
}
}
}
return 0;
sort(po.begin(),po.end());
ll m=0;
for(int i=0;i<n;i++){
s[i+1]+=s[i];
pl[po[i].i]=i+1;
s[i+1]+=w[po[i].i];
add(i+1,s[i+1]);
ans=max(ans,s[i+1]-m);
m=min(m,s[i+1]);
}
sort(q.begin(),q.end());
return 0;
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++){
int 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);
s[a]=s[a]-wa+wb;
}
for(int j=0;j<t.size();j++){
int a=pl[t[j].F],b=pl[t[j].S];
ans=max(ans,s[a]-mi(0,a,0,(1<<11)-1,0));
ans=max(ans,ma(a,n,0,(1<<11)-1,0)-s[a-1]);
ans=max(ans,s[b]-mi(0,b,0,(1<<11)-1,0));
ans=max(ans,ma(b,n,0,(1<<11)-1,0)-s[b-1]);
}
}
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:90:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int r=0;r<lin[j].size()-1-r;r++){
~^~~~~~~~~~~~~~~~~~
bulldozer.cpp:109:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<q.size();i++){
~^~~~~~~~~
bulldozer.cpp:112: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:116:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<t.size();j++){
~^~~~~~~~~
bulldozer.cpp:127:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<t.size();j++){
~^~~~~~~~~
bulldozer.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&n);
~~~~~^~~~~~~~~~~
bulldozer.cpp:72: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);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
