제출 #103923

#제출 시각아이디문제언어결과실행 시간메모리
103923Bodo171Bulldozer (JOI17_bulldozer)C++14
0 / 100
7 ms512 KiB
#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; }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 update(int nod,int l,int r,int poz,long long val) { A[poz]=val; } void query(int nod,int l,int r,int st,int dr) { long long sum=0; for(int i=st;i<=dr;i++) { sum+=A[i]; if(sum>ans.mxpref) ans.mxpref=1LL*sum; } sum=0; for(int i=dr;i>=st;i--) { sum+=A[i]; if(sum>ans.mxsuf) ans.mxsuf=1LL*sum; } } int abss(int x) { if(x<0) return -x; return x; } int main() { //freopen("data.in","r",stdin); cin>>n; for(i=1;i<=n;i++) { cin>>v[i].x>>v[i].y>>v[i].val; mx=max(mx,v[i].val); } sort(v+1,v+n+1,compP); 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=v[i].val+v[j].val; ans.mxpref=ans.sum=ans.mxsuf=0; if(i>=1)query(1,1,n,1,i-1); act+=ans.mxsuf; ans.mxpref=ans.sum=ans.mxsuf=0; if(j<n) query(1,1,n,j+1,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]); // if(abss(ord[I]-ord[J])!=1) // cout<<"assert\n"; 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=1LL*v[I].val+v[J].val; ans.mxpref=ans.sum=ans.mxsuf=0; if(poz>=1)query(1,1,n,1,poz-1); act+=ans.mxsuf; ans.mxpref=ans.sum=ans.mxsuf=0; if(poz+1<n)query(1,1,n,poz+2,n); act+=ans.mxpref; if(act>mx) mx=1LL*act; } cout<<mx; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...