记录编号	15289	评测结果	AAAAAAAAAA
题目名称	[USACO Mar07] 月度花费	最终得分	100
用户昵称	EnAsn	是否通过	通过
代码语言	Pascal	运行时间	0.106 s
提交时间	2009-11-11 15:26:29	内存使用	0.30 MiB

program ex;
type
 ss=array[1..100000]of integer;
var
 money:ss;
 n,m:longint;
 sum,temp:longint;
procedure init;
 var
  i:longint;
 begin
  assign(input,'expense.in');
  assign(output,'expense.out');
  reset(input);
  rewrite(output);
  readln(n,m);
  for i:=1 to n do
   begin
    readln(money[i]);
    sum:=sum+money[i];
   end;
  close(input);
 end;
procedure search(x,head,tail:longint);
 var
  i:longint;
  k,temp:longint;
 begin
  temp:=0;k:=0;
  for i:=1 to n do
   begin
    if money[i]>x then begin k:=n; break; end;
    if temp+money[i]<=x then temp:=temp+money[i]
                        else begin
                              inc(k);
                              temp:=money[i];
                             end;
   end;
  inc(k);
  if k<=m then
   begin
    if head=tail then
     begin
      writeln(head);
      close(output);
      halt;
     end
     else search((x+head)div 2,head,x);
   end
   else begin
         if head=tail then
          begin
           writeln(head);
           close(output);
           halt;
          end
          else search((x+tail)div 2,x+1,tail);
        end;
 end;
begin
 init;
 search(sum div 2,1,sum);
end.