记录编号	472506	评测结果	AAAAAAAAAA
题目名称	[USACO Mar07] 月度花费	最终得分	100
用户昵称	八级大狂风	是否通过	通过
代码语言	C++	运行时间	0.027 s
提交时间	2017-11-07 18:50:10	内存使用	0.67 MiB

#include <cstdio>
#include <algorithm>
#define ll long long 
using namespace std;

int n,m;
int a[100100];

bool check(ll x){
    ll ans=1;
    ll total=0;
    int i;
    for(i=1;i<=n;i++){
        if(total+a[i]<=x){
            total+=a[i];
        }else{
            if(a[i]>x)return 0;
            else{
                ans++;
                total=a[i];
            }
        }
    }
    if(ans<=m)return 1;
    return 0;
}
int main(){
    freopen("expense.in","r",stdin);
    freopen("expense.out","w",stdout);
    scanf("%d%d",&n,&m);
    ll i,l=1,r=0;
    for(i=1;i<=n;i++){
        scanf("%d",&a[i]);
        r+=a[i];
    }
    ll mid=(l+r)>>1;
    ll ans=-1;
    while(l<=r){
        mid=(l+r)>>1;
        if(check(mid)){
            r=mid-1;ans=mid;
        }else l=mid+1;
    }
    printf("%lld",ans);
    return 0;
}