bzoj 4590: [Shoi2015]自动刷题机

好恶心。。

二分上界到100000LL*1000000000LL  %_%

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
int n,m;LL a[110000];
int check(LL mid)
{
    LL sum=0,ss=0;
    for(int i=1;i<=n;i++)
    {
        sum+=a[i];
        if(sum>=mid){sum=0;ss++;}
        if(sum<0)sum=0;
    }
    if(ss==m)return 0;
    if(ss<m)return 1;
    else return 2;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    
    LL l,r;
    
    LL mmin=-1;
    l=1,r=100000LL*1000000000LL;
    while(l<=r)
    {
        LL mid=(l+r)/2;
        int d=check(mid);
              if(d==1)r=mid-1;
        else if(d==2)l=mid+1;
        else
        {
            r=mid-1;
            mmin=mid;
        }
    }
    
    LL mmax=-1;
    l=1,r=100000LL*1000000000LL;
    while(l<=r)
    {
        LL mid=(l+r)/2;
        int d=check(mid);
             if(d==1)r=mid-1;
        else if(d==2)l=mid+1;
        else
        {
            l=mid+1;
            mmax=mid;
        }
    }
    
    if(mmin==-1)printf("-1
");
    else printf("%lld %lld
",mmin,mmax);
    return 0;
}