比赛 |
皇后 |
评测结果 |
AAAAAAAAAA |
题目名称 |
划分数列 |
最终得分 |
100 |
用户昵称 |
Emine |
运行时间 |
0.034 s |
代码语言 |
C++ |
内存使用 |
1.06 MiB |
提交时间 |
2017-03-19 19:47:00 |
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn=101000;
int n,k,s[maxn],c[maxn],maxa;
int read()
{
int x=0;
char ch=getchar();
while(ch<='9'&& ch>='0')
{
x=x*10+ch-48;
ch=getchar();
}
return x;
}
bool cha(int len)
{
int sum=0,cn=1;
for(int i=1;i<=n;i++)
{
sum+=c[i];
if(sum>len)
cn++,sum=c[i];
}
return cn<=k;
}
int find()
{
int l=maxa,r=s[n],mid;
while(l<=r)
{
mid=(l+r)/2;
if(cha(mid))
r=mid-1;
else
l=mid+1;
}
return l;
}
int main()
{
freopen("seqa.in","r",stdin);
freopen("seqa.out","w",stdout);
n=read(),k=read();
for(int i=1;i<=n;i++)
{
c[i]=read();
s[i]=s[i-1]+c[i];
maxa=max(maxa,c[i]);
}
printf("%d\n",find());
return 0;
}