Cod sursa(job #895630)
#include <iostream>
#include <fstream>
using namespace std;
int ok(int m,int k,int a[],int n)
{
int i,nrt=0,sa=a[1];
for(i=1;i<n;i++)
{
if(sa+a[i+1]>m)
{
nrt++;
sa=a[i+1];
}
else
{
sa=sa+a[i+1];
}
}
if(nrt+1<=k)
return 1;
else return 0;
}
int main()
{
ifstream fin("transport.in");
ofstream fout("transport.out");
int li,lf,m,a[16001],max=0,s=0,n,k,i;
fin>>n>>k;
for(i=1;i<=n;i++)
fin>>a[i];
for(i=1;i<=n;i++)
{
if(a[i]>max)
max=a[i];
s=s+a[i];
}
li=max; lf=s;
while(li<=lf)
{
m=(li+lf)/2;
if(ok(m,k,a,n)) lf=m-1;
else li=m+1;
}
if (!ok(m,k,a,n)) ++m;
fout<<m;
return 0;
}