#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<db,db> pdb;
typedef tuple<int,int,int> tii;
typedef tuple<ll,ll,ll> tll;
typedef tuple<int,int,int,int> ti4;
typedef vector<vector<ll>> mat;
const ll mod=998244353,inf=1e18;
const int N=2005,M=5e7+5,K=1e5+5;
struct st{
ll dx,dy; int idx1,idx2;
}arr[N*N]; int cnt;
int n,rev[N];
ll s1,s2,ans;
struct point{
ll x,y,c;
}a[N];
ll mx[4*N],s[4*N],ls[4*N],rs[4*N];
void upd(int nd,int l,int r,int x,ll v){
if(l==r){
s[nd]=v; mx[nd]=ls[nd]=rs[nd]=max(0ll,v);
return;
}
int m=(l+r)>>1;
if(x<=m) upd(nd<<1,l,m,x,v);
else upd(nd<<1|1,m+1,r,x,v);
s[nd]=s[nd<<1]+s[nd<<1|1];
mx[nd]=max({mx[nd<<1],mx[nd<<1|1],rs[nd<<1]+ls[nd<<1|1]});
ls[nd]=max(ls[nd<<1],s[nd<<1]+ls[nd<<1|1]);
rs[nd]=max(rs[nd<<1|1],rs[nd<<1]+s[nd<<1|1]);
}
ll ccw(pll p1,pll p2,pll p3){
return p1.x*p2.y+p2.x*p3.y+p3.x*p1.y-p1.y*p2.x-p2.y*p3.x-p3.y*p1.x;
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y>>a[i].c;
sort(a+1,a+1+n,[](point p,point q){
return pll(p.x,p.y)<pll(q.x,q.y);
});
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
arr[++cnt]={a[j].x-a[i].x,a[j].y-a[i].y,i,j};
}
}
sort(arr+1,arr+1+cnt,[](st p,st q){
ll v=ccw(pll(0,0),pll(p.dx,p.dy),pll(q.dx,q.dy));
if(v) return v>0;
return pii(p.idx1,p.idx2)<pii(q.idx1,q.idx2);
});
for(int i=1;i<=n;i++){
rev[i]=i;
upd(1,1,n,i,a[i].c);
}
for(int i=1;i<=cnt;i++){
int ii=i;
while(ii+1<=n&&!ccw(pll(0,0),pll(arr[i].dx,arr[i].dy),pll(arr[ii+1].dx,arr[ii+1].dy))) ii++;
for(int j=i;j<=ii;j++){
int j1=arr[j].idx1,j2=arr[j].idx2;
int k1=rev[j1],k2=rev[j2];
swap(a[k1],a[k2]);
swap(rev[j1],rev[j2]);
upd(1,1,n,k1,a[k1].c);
upd(1,1,n,k2,a[k2].c);
}
ans=max(ans,mx[1]);
i=ii;
}
cout<<ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
504 KB |
Output is correct |
| 2 |
Correct |
6 ms |
504 KB |
Output is correct |
| 3 |
Correct |
6 ms |
504 KB |
Output is correct |
| 4 |
Correct |
6 ms |
504 KB |
Output is correct |
| 5 |
Correct |
6 ms |
504 KB |
Output is correct |
| 6 |
Correct |
6 ms |
504 KB |
Output is correct |
| 7 |
Correct |
6 ms |
504 KB |
Output is correct |
| 8 |
Correct |
6 ms |
504 KB |
Output is correct |
| 9 |
Correct |
6 ms |
504 KB |
Output is correct |
| 10 |
Correct |
6 ms |
504 KB |
Output is correct |
| 11 |
Correct |
5 ms |
504 KB |
Output is correct |
| 12 |
Incorrect |
5 ms |
380 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
504 KB |
Output is correct |
| 2 |
Correct |
6 ms |
504 KB |
Output is correct |
| 3 |
Correct |
6 ms |
504 KB |
Output is correct |
| 4 |
Correct |
6 ms |
504 KB |
Output is correct |
| 5 |
Correct |
6 ms |
504 KB |
Output is correct |
| 6 |
Correct |
6 ms |
504 KB |
Output is correct |
| 7 |
Correct |
6 ms |
504 KB |
Output is correct |
| 8 |
Correct |
6 ms |
504 KB |
Output is correct |
| 9 |
Correct |
6 ms |
504 KB |
Output is correct |
| 10 |
Correct |
6 ms |
504 KB |
Output is correct |
| 11 |
Correct |
5 ms |
504 KB |
Output is correct |
| 12 |
Incorrect |
5 ms |
380 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
504 KB |
Output is correct |
| 2 |
Correct |
6 ms |
504 KB |
Output is correct |
| 3 |
Correct |
6 ms |
504 KB |
Output is correct |
| 4 |
Correct |
6 ms |
504 KB |
Output is correct |
| 5 |
Correct |
6 ms |
504 KB |
Output is correct |
| 6 |
Correct |
6 ms |
504 KB |
Output is correct |
| 7 |
Correct |
6 ms |
504 KB |
Output is correct |
| 8 |
Correct |
6 ms |
504 KB |
Output is correct |
| 9 |
Correct |
6 ms |
504 KB |
Output is correct |
| 10 |
Correct |
6 ms |
504 KB |
Output is correct |
| 11 |
Correct |
5 ms |
504 KB |
Output is correct |
| 12 |
Incorrect |
5 ms |
380 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
