Fast Food UVA - 662

#include "bits/stdc++.h"
using namespace std;
 #define N 1003
 int m,n,a[N],c[N][N],f[N][N],p[N][N];
 
 void print_path(int i, int j){
    if (i <= 0)
        return;
    int k = p[i][j];
    print_path(k,j-1);
    if (k + 1 == i)
        printf("Depot %d at restaurant %d serves restaurant %d\n", j, (k + 1 + i) >> 1, k+ 1);
    else
        printf("Depot %d at restaurant %d serves restaurants %d to %d\n", j, (k + 1 + i) >> 1, k + 1, i);
 }


 void sov(int cas){
 	int i,j,k;
 	for(i=1;i<=n;i++) cin>>a[i] ;
 	for(i=1;i<=n;i++)
 	 for(j=i+1;j<=n;j++)
 	  c[i][j]=c[i][j-1]+a[j]-a[(i+j)/2];
 	  
 	memset(f,127,sizeof f);
 	for(i=1;i<=n;i++) f[i][1]=c[1][i];
 	
 	for(i=2;i<=n;i++)
 	 for(j=2;j<=m&&j<=i;j++)
 	  for(k=j-1;k<i;k++){
 	  	int t =f[k][j-1]+c[k+1][i];
 	  	if(f[i][j]>t) p[i][j]=k,f[i][j]=t;
 	  }
 	printf("Chain %d\n",cas);
        print_path(n,m);
        printf("Total distance sum = %d\n\n",f[n][m]);
 	//cout<<f[n][m]<<endl;
 }
 signed main(){
 	int cas=0;
 	while(cin>>n>>m){ if(n==0&&m==0) break; sov(++cas); }
 }