记录编号	416908	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[SHOI 2015] 自动刷题机	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	0.404 s
提交时间	2017-06-23 09:35:11	内存使用	1.08 MiB

# include <bits/stdc++.h>
# define MAXN 100023
# define mid ((l + r) >> 1)
using namespace std;

long long a[MAXN], k, n, maxa, ansl = -1, ansr = -1;

inline long long check(long long x) { 
    long long ans = 0, temp = 0;
    for(long long i = 1; i <= n; i++) { 
        temp += a[i];
        ans += (temp >= x);
        if(temp >= x || temp < 0) temp = 0;
    }
    return (ans > k) - (ans < k);
    //ans > k  return 1      x < 
    //ans < k  return -1     x >
    //ans == k return 0      x bl
    //  
    //  1 1 2 2 2 2 2 3 3
    //    l r       l r  
}

int main() { 
# ifndef LOCAL
    freopen("autoac.in", "r", stdin);
    freopen("autoac.out", "w", stdout);
# else 
    freopen("in", "r", stdin);
# endif
    scanf("%lld%lld", &n, &k);
    for(long long i = 1; i <= n; i++) { 
        scanf("%lld", a + i);
        maxa += (a[i] > 0) ? a[i] : 0;
    }
    long long l = 1, r = maxa;
    while((l + 1) ^ r) { 
        if(check(mid) == 1) l = mid;
        else r = mid;
    }
    if(!check(l)) ansl = l;
    else if(!check(r)) ansl = r;

    l = 1, r = maxa;
    while((l + 1) ^ r) { 
        if(check(mid) > -1) l = mid;
        else r = mid;
    }
    if(!check(r)) ansr = r;
    else if(!check(l))ansr = l;
    if(!~ansl && !~ansr) { 
        printf("-1\n");
    } else printf("%lld %lld\n", ansl, ansr);
}