记录编号 18033 评测结果 AAAAAAAAAA
题目名称 [USACO Mar07] 月度花费 最终得分 100
用户昵称 Gravatarreamb 是否通过 通过
代码语言 Pascal 运行时间 0.099 s
提交时间 2010-09-06 21:12:08 内存使用 0.49 MiB
显示代码纯文本
program yueduhuafei;
var
  n,m,mid,sum,i,max,t,s,jilu:longint;
  a:array[1..100000] of longint;
procedure find(p,q:longint);
begin
  mid:=(p+q) div 2;
  t:=1;
  s:=0;
  for i:=1 to n do
    if s+a[i]<=mid then
      s:=s+a[i]
    else
    begin
      s:=a[i];
      t:=t+1
    end;
  if t<=m then
    if mid<jilu then
      jilu:=mid;
  if p=q then
  begin
    writeln (jilu);
    close (input);
    close (output);
    halt
  end;
  if t>m then
    find(mid+1,q)
  else
    find(p,mid-1)
end;
begin
  assign (input,'expense.in');
  reset (input);
  assign (output,'expense.out');
  rewrite (output);
    readln (n,m);
    jilu:=maxlongint;
    sum:=0;
    max:=0;
    for i:=1 to n do
    begin
      readln(a[i]);
      sum:=sum+a[i];
      if a[i]>max then
        max:=a[i]
    end;
    find (max,sum)
end.