Cod sursa(job #1496163)
Utilizator | Cioltan Andrei andy1207 | Data | 4 octombrie 2015 15:07:16 |
---|---|---|---|
Problema | Transport | Scor | 40 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.85 kb |
#include<cstdio>
int v[16201];
int main()
{
int n,k,max,s,e,i,q,st,dr,m,p,t;
freopen("transport.in","r",stdin);
freopen("transport.out","w",stdout);
scanf("%d%d",&n,&k);
max=s=0;
for(i=1;i<=n;i++)
{
scanf("%d",&v[i]);
if(v[i]>max)
max=v[i];
s+=v[i];
}
/*q=max;
for(i=1;q<=s;i++)
{
v1[i]=q;
q++;
}*/
st=1;
dr=i;
e=0;
while(st<=dr)
{
m=(st+dr)/2;
p=max+m-1;
t=0;
for(i=1;i<=n;i++)
{
s=0;
while(s+v[i]<=p && i<=n)
{
s+=v[i];
i++;
}
t++;
i--;
}
if(t<=k)
{
e=max+m-1;
dr=m-1;
}
else
st=m+1;
}
printf("%d\n",e);
return 0;
}