题目来源：http://acm.nyist.edu.cn/problem/1664

题目描述:

天降伟人PK又公开了他的新发明：AC自动机——一种可以自动 AC 题目的神秘装置。
AC自动机刷题的方式非常简单：首先会瞬间得出题目的正确做法，然后开始写程序。每秒，AC自动机的代码生成模块会有两种可能的结果：
１.写了x 行代码；
2.心情不好，删掉了之前写的 行代码。如果 大于当前代码长度，则相当于全部删除。
对于 NYOJ，存在某个固定的长度n(n>0)，一旦AC自动机在某秒结束时积累了大于等n行的代码，它就会自动提交并AC此题，然后新建一个文件(即弃置之前的所有代码)并开始写下一题,PK 在 NYOJ 上跑了一天的AC自动机，得到了很多条关于写代码的日志信息。他突然发现自己没有记录 NYOJ 的n究竟是多少。所幸他通过自己 NYOJ 上的 Rank 知道了AC自动机一共切了k道题，希望你计算n可能的最小值和最大值。

输入描述:

第一行两个整数 l, k( 1 <= l <= 10^5,1 <= k <= 10^4)，表示刷题机的日志一共有 l 行，一共了切了 k 题。
第二行 l 个整数 x_1, ……, x_l。x_i >= 0 表示写了 x_i 行代码，x_i < 0 表示删除了这道题的 -x_i 行代码(-10^9 <= x_i <= 10^9)。

输出描述：

输出两个数 a, b，分别代表 n 可能的最小值和最大值。如果不存在这样的 n 则输出 -1。

样例输入：
5 5
1000000000
1000000000
1000000000
1000000000
1000000000
4 2
2
5
-3
9
样例输出:
1 1000000000
3 7

比赛比较自闭其他题都没咋看，尤其是没啥人ａ的：
这是一道不难的二分题，切题数关于ｎ具有单调性，ｎ越大切的题就越少，这里要求可能的最小值（ans_l)与最大值(ans_r)，写个check函数检验二分的答案，显然如果check(mid)>k(另外一个是>=),ans_l要加１，因为>k求出的是满足check(mid)>k的最大值,而我们要的是check(mid)==k的最小值.同理ans_r则需要减一.（二分边界搞为inf就wa改1e11+5就ａ了，迷＝_=

参考代码：

/** 5 5 1000000000 1000000000 1000000000 1000000000 1000000000 1 1000000000 4 2 2 5 -3 9 3 7 **/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
#define ll long long
const int N = 1e5+5;
const ll M = 1e11+5;
#define max(a,b) a>b?a:b
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
ll n,k,a[N],l,r,ans_l,ans_r;
ll check(ll x)//对应ｘ的切题数
{
   ll now=0,num=0;
   for (ll i=1;i<=n;i++){
       now=max(now+a[i],0);
       if (now>=x)num++,now=0;
   }
   return num;
}
int main() {
   //freopen("//home/nuoyanli//文档//0615//D//data//secret//autoac2.in", "rep", stdin);
   while (cin >> n >> k) {
       for (int i = 1; i <= n; i++) {
           cin >> a[i];
       }
       l = 1, r = M, ans_l = 0, ans_r = 0;
       while (l <= r) {
           ll mid = (l + r) / 2;
           if (check(mid) > k) {
               ans_l = mid, l = mid + 1;
           } else {
               r = mid - 1;
           }
       }
       l = 1, r = M;
       while (l <= r) {
           ll mid = (l + r) / 2;
           if (check(mid) < k) {
               ans_r = mid, r = mid - 1;
           } else {
               l = mid + 1;
           }
       }
       ans_l++;
       ans_r--;
       if (check(ans_l) != k || check(ans_r) != k) {
           cout << "-1" << endl;
       } else {
           cout << ans_l << " " << ans_r << endl;
       }
   }
   return 0;
}