[APIO2014]序列分割

#include
#include#define N 100009
#define M 202
#define double long double 
using namespace std;
typedef long long ll;
ll dp[2][N],sum[N],n,k,h,t;
int id[M][N];
inline ll rd(){
    ll x=0;char c=getchar();bool f=0;
    while(!isdigit(c)){if(c==‘-‘)f=1;c=getchar();}
    while(isdigit(c)){x=(x1)+(x3)+(c^48);c=getchar();}
    return f?-x:x;
}
struct point{
  double x,y;int id;
  double operator *(const point &b)const{return x*b.y-y*b.x;}
  point operator -(const point &b)const{return point{x-b.x,y-b.y,0};}
  double operator /(const point &b)const{
      if(b.x==x){
          if(b.y-y>0)return 2e15;
          else return -2e15;
      }
    return (b.y-y)/(b.x-x);
  }
}q[N];
void dfs(int now,int idd){
    if(!now)return;
    if(id[now][idd])dfs(now-1,id[now][idd]);
    printf("%d ",idd);
}
int main(){
//    freopen("1.in","r",stdin);
    n=rd();k=rd();
    for(int i=1;i1];
    int now=1,pre=0;
    for(int i=1;ii){
        h=1;t=0;
        swap(now,pre);
        for(int j=1;jj){
            point x=point{(double)sum[j-1],(double)dp[pre][j-1]-sum[j-1]*sum[n],j-1};
            while(h1])*(x-q[t])>=0)t--;q[++t]=x;
            while(h1]/q[h]))h++;
            dp[now][j]=q[h].x*sum[j]+q[h].y+sum[n]*sum[j]-sum[j]*sum[j];
            id[i][j]=q[h].id;
        }
    }
    ll ans=0,idd;
    for(int i=1;ii)
      if(dp[now][i]>ans){
        ans=dp[now][i];idd=i;
      }
    coutendl;
    dfs(k,idd);
    return 0;
}