记录编号	302940	评测结果	AAAAAAAAAA
题目名称	[USACO Mar07] 月度花费	最终得分	100
用户昵称	残星誓言	是否通过	通过
代码语言	C++	运行时间	0.132 s
提交时间	2016-09-04 19:04:20	内存使用	1.08 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
long long a[100000+100];
int n,k;
long long TP;
long long  l=-2147483647; long long r=0;
bool check(long long x)
{    long long now=0;//long long last=0;
	 int num=1;
	 //if(TP>x) return false;
	 for(int i=1;i<=n;i++)
     {
			 now+=a[i];
			 if(now>x)
			 {
				  num++;
				  if(now!=x)
				  now=a[i];
				  else
				  now=0;
				  //printf("%d %d %d\n",a[i],now,num);
			 }
			  //printf("%I64d %I64d %d\n",a[i],now,num);

     }
     if(num<=k)
     return 1; else return 0;
}
int main()
{
   freopen("expense.in","r",stdin);
   freopen("expense.out","w",stdout);

   scanf("%d%d",&n,&k);
   for(int i=1;i<=n;i++)
   {
		 cin>>a[i]; l=max(l,a[i]); r+=a[i]; //TP=max(TP,a[i]);
   }

   while(l<=r)
   {     //cout<<l<<' '<<r<<endl;
		 long long  mid=(l+r)/2;
		 if(check(mid))
		 r=mid;
		 else
		 l=mid+1;

		 if(l==r)
		 {
		   printf("%d",l);
		   break;
		 }
   }
   //cout<<"changweiming"<<endl;
   /*if(check(9))printf("yes");
	 else printf("wrong");*/
	// while(1);
   return 0;
}