Cod sursa(job #52683)

Utilizator kyrkDragos Dumitrescu kyrk Data 19 aprilie 2007 18:24:15
Problema Transport Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include<stdio.h>
main()
{
long n,k,i,j,max=0,m,x,s=0,t;
long aux,sp,valid,ind,fin,min,dd=25601;
int a[16001];
freopen("transport.in","r",stdin);
freopen("transport.out","w",stdout);
fscanf(stdin,"%lld%lld",&n,&k);
for(i=1;i<=n;i++)
{ fscanf(stdin,"%d",&a[i]);
  if(a[i]>max)max=a[i];
  s+=a[i];
}
ind=max;
fin=s;
sp=0;
do{
   x=fin-ind;x/=2;
   x=ind+x;
   i=1;t=0;
   x=7;
   do{
      valid=0;
      s=0;
      s+=a[i];
      i++;
      do{
	  if((s+a[i])<=x){s+=a[i];i++;}
	  else{ valid=1; t++;s=0; }
	 }while((valid==0)&&(i<=n));
      if((s>0)&&(t<=x))t++;

      }while(i<=n);
   if(t<=k) {  if(x<=dd)dd=x;
	       fin=x;
	    }
   else ind=x;
   }while(fin-ind==14);












fclose(stdin);
fclose(stdout);
}