제출 #943970

#제출 시각아이디문제언어결과실행 시간메모리
943970Warinchai수열 (APIO14_sequence)C++14
89 / 100
622 ms87112 KiB
#include<bits/stdc++.h> using namespace std; int ar[100005]; struct line{ long long m,c; int num; line(long long mm=0,long long cc=0,long long i=0){ m=mm; c=cc; num=i; } long long pnt(long long x){ return m*x+c; } }; bool better(line a,line b,line c){ return (c.c-a.c)*(a.m-b.m)<=(b.c-a.c)*(a.m-c.m); } struct hull{ deque<line>dq; void add(line x){ while(dq.size()>1&&better(dq[dq.size()-2],dq.back(),x)){ dq.pop_back(); } dq.push_back(x); } pair<long long,int> fbest(long long x,int mxl){ while(dq.size()>1&&dq.front().num<mxl&&(dq.front().pnt(x)<dq[1].pnt(x))){ dq.pop_front(); } if(dq.empty()){ return {0,0}; } return {dq.front().pnt(x),dq.front().num}; } }hl; long long sum[100005]; int path[205][100005]; line info[2][100005]; vector<int>v; int main(){ int n,k; cin>>n>>k; long long sm=0; for(int i=1;i<=n;i++){ cin>>ar[i]; sm+=ar[i]; sum[i]=sm; } long long ans=0; long long lnum=0; //cerr<<"work"<<endl; for(int i=1;i<=k;i++){ hl.dq.clear(); for(int j=i;j<n;j++){ //cerr<<"i:j "<<i<<" "<<j<<endl; if(i!=1){ hl.add(info[i%2][j-1]); } pair<long long,int>p=hl.fbest(sum[j],j); //cerr<<"after fbest"<<endl; long long x=p.first; //cerr<<"x:"<<x<<endl; int pn=p.second; long long tans=x+sm*sum[j]-sum[j]*sum[j]; //cerr<<"ans:"<<tans<<endl; long long nm=sum[j]; long long nc=tans-sm*sum[j]; info[(i+1)%2][j]=(line(nm,nc,j)); //cerr<<"after add"<<endl; path[i][j]=pn; if(i==k){ if(tans>ans){ ans=tans; lnum=j; } } } } //cerr<<"out"<<endl; cout<<ans<<"\n"; v.push_back(lnum); for(int i=k;i>=2;i--){ lnum=path[i][lnum]; v.push_back(lnum); } for(int i=v.size()-1;i>=0;i--){ cout<<v[i]<<" "; } }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...