Cod sursa(job #40168)

Utilizator andrewgPestele cel Mare andrewg Data 27 martie 2007 11:45:48
Problema Transport Scor 0
Compilator fpc Status done
Runda Arhiva de probleme Marime 0.9 kb
const maxn = 16000;

var f:text;
    n,k,i,j,mid:longint;
    a:array[1..maxn]of longint;
    s,t:longint;
    ok:boolean;

procedure readdata;
begin
   assign(f,'transport.in');
   reset(f);
   readln(f,n,k);
   for i:=1 to n do
   begin
      readln(f,a[i]);
      s:=s+a[i];
   end;
   close(f);
end;

procedure solve(x,y:longint);
begin
   if x=y then
   begin
      assign(f,'transport.out');
      rewrite(f);
      writeln(f,x);
      close(f);
      halt(1);
   end;
   mid:=(x+y) div 2;
   j:=0;
   t:=0;
   ok:=false;
   for i:=1 to n do
   begin
      if a[i]>mid then
      begin
         ok:=true;
         break;
      end;
      t:=t+a[i];
      if t>mid then
      begin
         inc(j);
         t:=a[i];
      end;
   end;
   if j>=k then ok:=true;
   if ok then solve(mid+1,y)
         else solve(x,mid);
end;

begin
   readdata;
   solve(1,s);
end.