Cod sursa(job #815549)
Utilizator | Data | 17 noiembrie 2012 10:35:09 | |
---|---|---|---|
Problema | Transport | Scor | 60 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.58 kb |
#include<stdio.h>
int v[16001],i,j,max,nr,st,dr,s2,s,pp,m,n,k,cate;
int main()
{
FILE *f,*g;
f=fopen("transport.in","r");
g=fopen("transport.out","w");
fscanf(f,"%d%d",&n,&k);
for(i=1;i<=n;i++)
{
fscanf(f,"%d",&v[i]);
if(v[i]>max) max=v[i];
s+=v[i];
}
st=max-1;
dr=s+1;
while(st<=dr)
{
m=(st+dr)/2;
j=1;
cate=0;
for(nr=1;nr<=n&&j<=n;nr++)
{
s2=0;
cate++;
// j=1;
while(s2+v[j]<=m&&j<=n)
{
s2+=v[j];
j++;
}
}
if(cate<=k)
{
dr=m-1;
}
else st=m+1;
}
fprintf(g,"%d",m);
return 0;
}