记录编号	431786	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	2642.[SHOI 2015] 自动刷题机	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	0.658 s
提交时间	2017-08-01 19:16:27	内存使用	0.70 MiB

#include<bits/stdc++.h>
using namespace std;
int l,k,a[100005];
long long ma=0;
bool pd_max(long long x)
{
	long long ans=0;
	int cnt=0;
	for(int i=1;i<=l;i++)
	{
		ans+=a[i];
		if(ans<0)
		ans=0;
		if(ans>=x)
		{
			cnt++;
			ans=0;
		}
	}
	if(cnt>=k)
	return 1;
	else
	return 0;
}
bool pd_min(long long x)
{
	long long ans=0;
	int cnt=0;
	for(int i=1;i<=l;i++)
	{
		ans+=a[i];
		if(ans<0)
		ans=0;
		if(ans>=x)
		{
			cnt++;
			ans=0;
		}
	}
	if(cnt>k)
	return 1;
	else
	return 0;
}
int main()
{
	freopen("autoac.in","r",stdin);
	freopen("autoac.out","w",stdout);
//	freopen("1.txt","r",stdin);
	scanf("%d%d",&l,&k);
	for(int i=1;i<=l;i++)
	{
		scanf("%d",&a[i]);
		if(a[i]>0)
		ma+=a[i];
	}
	long long L=1,r=ma;
	while(L!=r)
	{
		long long mid=((L+r)>>1)+1;
		if(pd_max(mid))
		L=mid;
		else
		r=mid-1;
	}
	long long x1=L;
	L=1,r=ma;
	while(L!=r)
	{//cout<<L<<" "<<r<<endl;
		long long mid=(L+r)>>1;
		if(pd_min(mid))
		L=mid+1;
		else
		r=mid;
	}
	long long x2=L;//无解一开始没想出来怎么处理，看了别人的，其实只需要把最终分出来的答案再带进去检验一下就可以了 
	if(x2>x1)
	{
		cout<<-1;
		return 0;
	}
	if(!pd_min(x2)&&pd_max(x1))
	cout<<x2<<" "<<x1;
	else
	{
		cout<<-1;
	}
	return 0;
}