#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<complex>
#include<math.h>
#include<unordered_set>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef complex<long double> C;
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
#define mad(a,b) a=(a+b)%mod
#define PI acosl(-1)
#define N 2010
ll n,x[N],y[N],w[N];
ll dat1[2*N],dat2[2*N],dat3[2*N];
void init(){
rep(i,2*N){
dat1[i]=1e17;
dat2[i]=-1e17;
dat3[i]=-1e17;
}
}
void upd(ll i,ll x){
//cout<<"update"<<i<<" "<<x<<" ";
i+=N;
dat1[i]=dat2[i]=x;
for(;i>1;i>>=1){
dat1[i/2]=min(dat1[i],dat1[i^1]);
dat2[i/2]=max(dat2[i],dat2[i^1]);
int a=i,b=i^1; if(a>b)swap(a,b);
dat3[i/2]=max(dat2[b]-dat1[a],max(dat3[a],dat3[b]));
}
//cout<<dat3[1]<<endl;
}
ll rsm(){
return dat3[1];
}
ll pl[N];
ll swp(int a,int b){//cout<<"swp"<<w[a]<<" "<<w[b]<<endl;
if(pl[a]>pl[b])swap(a,b);
ll base=dat1[N+pl[a]];
upd(pl[a]+1,base+w[b]);
swap(pl[a],pl[b]);//cout<<"rsm"<<rsm()<<endl;
return rsm();
}
struct qry{
ld arg;
ll a,b;
bool operator<(const qry&key)const{
return this->arg<key.arg;
}
};
int main(){
cin>>n;
rep(i,n){
cin>>x[i]>>y[i]>>w[i];
}
rep(i,n)rep(j,n-1){
bool sw=0;
if(y[j]!=y[j+1])sw=y[j]>y[j+1];
else if(x[j]!=x[j+1])sw=x[j]<x[j+1];
if(sw){
swap(x[j],x[j+1]);
swap(y[j],y[j+1]);
swap(w[j],w[j+1]);
}
}
init();
ll rui=0;
upd(0,rui);
rep(i,n){
rui+=w[i];
upd(i+1,rui);
pl[i]=i;
}
vector<qry> Q;
rep(i,n)rep(j,i){
ld vl=atan2(y[i]-y[j],x[i]-x[j]);
ld vr=atan2(y[j]-y[i],x[j]-x[i]);
//cout<<"atan"<<w[i]<<" "<<w[j]<<" "<<vl<<" "<<vr<<endl;
Q.push_back((struct qry){max(vl,vr),i,j});
}
sort(all(Q));
ll ans=0;
chmax(ans,rsm());
rep(i,Q.size()){
chmax(ans,swp(Q[i].a,Q[i].b));
}
cout<<ans<<endl;
}
Compilation message
bulldozer.cpp: In function 'int main()':
bulldozer.cpp:18:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i,n) for(int i=0;i<n;i++)
bulldozer.cpp:100:9:
rep(i,Q.size()){
~~~~~~~~~~
bulldozer.cpp:100:5: note: in expansion of macro 'rep'
rep(i,Q.size()){
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
