Cod sursa(job #483857)
Utilizator | Stanca Marian Ciprian CS-me | Data | 10 septembrie 2010 14:53:08 |
---|---|---|---|
Problema | Transport | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.78 kb |
#include<stdio.h>
FILE *fin, *fout;
int n,k,i,m,v[16001],p,nr,s,min,a,b;
int main(){
fin=fopen("trans.in","r");
fout=fopen("trans.out","w");
fscanf(fin,"%d %d",&n,&k);
for(i=1;i<=n;i++){
fscanf(fin,"%d",&v[i]);
b+=v[i];
}
if(b%k==0){
a=b/k;
}
else{
a=b/k+1;
}
while(a<=b){
m=(a+b)/2;
nr=0;
s=0;
for(i=1;i<=n && nr<k;i++){
if(s+v[i]<=m){
s+=v[i];
}
else{
s=v[i];
nr++;
}
}
if(s>0){
nr++;
s=0;
}
if(nr<=k){
min=m;
b=m-1;
}
else{
a=m+1;
}
}
fprintf(fout,"%d",min);
return 0;
}