이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;
const int nmax=2005;
struct point
{
long long x,y,val;
}v[nmax];
struct line
{
long long nr,nm;
int i1,i2;
}pp[nmax*nmax/2];
struct node
{
long long mxsuf,mxpref,sum;
}arb[4*nmax],ans;
pair<long long,long long> lin=make_pair(-2*1000*1000*1000-1,1);
bool compP(point unu,point doi)
{
return (1LL*unu.x*lin.first+1LL*unu.y*lin.second<1LL*doi.x*lin.first+1LL*doi.y*lin.second);
}
bool compL(line unu,line doi)
{
return (1LL*unu.nr*doi.nm<1LL*unu.nm*doi.nr);
}
int ord[nmax];
long long A[nmax];
int n,i,j,nr,I,J,poz;
long long act,mx;
void mrg(node &A,node B,node C)
{
A.sum=1LL*B.sum+C.sum;
A.mxpref=max(B.mxpref,B.sum+C.mxpref);
A.mxsuf=max(C.mxsuf,C.sum+B.mxsuf);
}
void update(int nod,int l,int r,int poz,long long val)
{
if(l==r)
{
arb[nod].mxpref=arb[nod].mxsuf=max(val,0LL);
arb[nod].sum=val;
return;
}
int m=(l+r)/2;
if(poz<=m) update(2*nod,l,m,poz,val);
else update(2*nod+1,m+1,r,poz,val);
mrg(arb[nod],arb[2*nod],arb[2*nod+1]);
}
void query(int nod,int l,int r,int st,int dr)
{
if(st<=l&&r<=dr)
{
mrg(ans,ans,arb[nod]);
return;
}
int m=(l+r)/2;
if(st<=m) query(2*nod,l,m,st,dr);
if(m<dr) query(2*nod+1,m+1,r,st,dr);
}
int abss(int x)
{
if(x<0) return -x;
return x;
}
void slv()
{
for(int i=1;i<=n;i++)
{
act=0;
for(int j=i;j<=n;j++)
{
act+=v[j].val;
if(act>mx)
mx=act;
}
}
}
int main()
{
//freopen("data.in","r",stdin);
cin>>n;
bool solve0=1;
for(i=1;i<=n;i++)
{
cin>>v[i].x>>v[i].y>>v[i].val;
mx=max(mx,v[i].val);
if(v[i].y!=0)
solve0=0;
}
sort(v+1,v+n+1,compP);
if(solve0)
{
slv();
cout<<mx;
return 0;
}
for(i=1;i<=n;i++)
{
ord[i]=i;
update(1,1,n,i,v[i].val);
}
for(i=1;i<=n;i++)
for(j=i+1;j<=n;j++)
if(v[i].x==v[j].x)
{
act=0;
ans.mxpref=ans.sum=ans.mxsuf=0;
if(i>=1)query(1,1,n,1,i);
act+=ans.mxsuf;
ans.mxpref=ans.sum=ans.mxsuf=0;
if(j<=n) query(1,1,n,j,n);
act+=ans.mxpref;
if(act>mx)
mx=1LL*act;
}
else
{
pp[++nr]={v[j].y-v[i].y,v[j].x-v[i].x,i,j};
if(pp[nr].nm<0)
pp[nr].nr*=-1,pp[nr].nm*=-1;
}
sort(pp+1,pp+nr+1,compL);
for(i=1;i<=nr;i++)
{
I=pp[i].i1;J=pp[i].i2;
swap(ord[I],ord[J]);
poz=min(ord[I],ord[J]);
update(1,1,n,ord[I],v[I].val);
update(1,1,n,ord[J],v[J].val);
act=0;
ans.mxpref=ans.sum=ans.mxsuf=0;
if(poz>=1)query(1,1,n,1,poz);
act+=ans.mxsuf;
ans.mxpref=ans.sum=ans.mxsuf=0;
if(poz+1<=n)query(1,1,n,poz+1,n);
act+=ans.mxpref;
if(act>mx)
mx=1LL*act;
}
cout<<mx;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |