lightoj1048

CODE

#include <iostream>
#include <cstdio>
using namespace std;
int a[1005];
int ncase;
int main()
{
        int t;
        scanf("%d",&t);
        while(t--)
        {
                int n,k;
                scanf("%d%d",&n,&k);
                int sum=0;
                for(int i=0;i<n+1;i++)
                {
                        scanf("%d",a+i);
                        sum+=a[i];
                }
                int l=0,r=sum;
                while(l<r)
                {
                        int mid=l+r>>1;
                        int cur=0;
                        int nseg=1;
                        int f=0;
                        for(int i=0;i<n+1;i++)
                        {
                                if(a[i]>mid)f=1;
                                if(cur+a[i]<=mid)cur+=a[i];
                                else
                                {
                                        cur=a[i];
                                        nseg++;
                                }
                        }
                        if(nseg>k+1||f)
                        {
                                l=mid+1;
                        }
                        else
                        {
                                r=mid;
                        }
                }
                printf("Case %d: %d\n",++ncase,l);
               // cout <<"Case "<<++ncase<<": "<<l<<endl;
                int nseg=0;
                int cur=0;
                for(int i=0;i<n+1;i++)
                {
                        cur+=a[i];
                        if(cur>l||k+1-nseg>=n+2-i)
                        {
                                cur-=a[i];
                                printf("%d\n",cur);
                                cur=a[i];
                                nseg++;
                        }
                }
                printf("%d\n",cur);

        }
        return 0;
}