Cod sursa(job #816401)
Utilizator | zurzic zeljko zurzic_doru | Data | 17 noiembrie 2012 12:38:39 |
---|---|---|---|
Problema | Transport | Scor | 80 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.88 kb |
#include<stdio.h>
using namespace std;
int main()
{
int max,s,n,k,v[16001],l1,l2,partial,nrt,rez,m,i;
freopen("transport.in","r",stdin);
freopen("transport.out","w",stdout);
scanf("%d%d",&n,&k);
max=0;
s=0;
for(i=1;i<=n;i++)
{
scanf("%d",&v[i]);
if(v[i]>max)
max=v[i];
s+=v[i];
}
l1=max-1;
l2=s+1;
while(l1<=l2)
{
m=(l1+l2)/2;
nrt=0;
partial=0;
for(i=1;i<=n;i++)
{
if((partial+v[i])<=m)
partial+=v[i];
else
{
nrt++;
partial=v[i];
}
}
nrt++;
if(nrt<=k)
l2=m-1;
else
l1=m+1;
if(nrt==k)
rez=m;
}
printf("%d",rez);
return 0;
}