> 按 lunatic 说的方法做,不知哪里理解错了,一直TLE,一开始的上下界用了部分和最大最小
> 
> #include "stdio.h"
> #include "stdlib.h"
> #include<algorithm>
> using namespace std;
> 
> const int M = 20001;
> 
> int a[M];
> int n, k;
> __int64 suml[M], sumr[M];
> int topl, topr;
> 
> inline bool scmp(__int64 a,__int64 b)
> {	return a<b;		}
> 
> int count( __int64 x, int l, int r )
> {
> 	if( l + 1 == r ) return a[l]<= x;
> 	int ret = 0;
> 	int mid = (l+r)>>1;
> 	ret += count( x, l, mid );
> 	ret += count( x, mid, r );
> 	int i,j;
> 	suml[0] = 0;
> 	for( j = 1, i = mid-1; i >= l; i --, j ++)
> 		suml[j] = suml[j-1] + a[i];
> 	topl = j;
> 	sumr[0] = 0;
> 	for( j = 1, i = mid; i < r; i ++, j ++ )
> 		sumr[j] = sumr[j-1] + a[i];
> 	topr = j;
> 	sort(suml+1,suml+topl,scmp);
> 	sort(sumr+1,sumr+topr,scmp);
> 	i = 1; j = topr-1;
> 	while( j && i != topl )
> 	{
> 		if( suml[i] + sumr[j] <= x )
> 			ret += j, i ++;
> 		else
> 			j --;
> 	}
> 	return ret;
> }
> 
> int main()
> {
> 	int c = 1;
> 	while( scanf( "%d%d", &n, &k ) != EOF )
> 	{
> 		int i;
> 		__int64 sum , isum,s1=0,s2=0;
> 		sum = isum = 0;
> 		for( i = 0; i < n; i ++ )
> 			scanf( "%d", &a[i] );
> 		for(i=0;i<n;i++)
> 		{
> 			s1+=a[i];
> 			s2+=a[i];
> 			if(s1<0)s1=0;
> 			if(s2>0)s2=0;
> 			if(s1>sum)sum=s1;
> 			if(s2<isum)isum=s2;
> 		}
> 		__int64 mid, l = isum, r = sum;
> 		while( l + 1 < r )
> 		{
> 			mid = (l + r)/2;
> 			if( count(mid,0,n) >= k )
> 				r = mid;
> 			else
> 				l = mid;
> 		}
> 		if( count(l,0,n) >= k )
> 			r = l;
> 		printf( "Case %d: %I64d\n", c++, r );
> 	}
> 	return 0;
> }