记录编号 15263 评测结果 AAAAAAAAAA
题目名称 [USACO Mar07] 月度花费 最终得分 100
用户昵称 GravatarZhouZn1 是否通过 通过
代码语言 Pascal 运行时间 0.104 s
提交时间 2009-11-11 12:56:05 内存使用 0.49 MiB
显示代码纯文本
program expense;
var
        n,m,i,j,summ:longint;
        a:array[1..100000]of longint;
procedure swap(var a,b:longint);
var
        t:longint;
begin
        t:=a;
        a:=b;
        b:=t;
end;

procedure init;
begin
        assign(input,'expense.in');
        reset(input);
        assign(output,'expense.out');
        rewrite(output);
        readln(n,m);
        summ:=0;
        for i:=1 to n do
        begin
        readln(a[i]);
        inc(summ,a[i]);
        end;

end;
function check(x:longint):boolean;
var
        sum,i,num:longint;
begin
        sum:=0;
        num:=0;
        for i:=1 to n do
        begin
             if num+1>m then exit(false);
             if sum+a[i]<=x then
             inc(sum,a[i]) else
             if sum>x then exit(false) else
             if sum<=x then
             begin
                inc(num);
                sum:=a[i];
                if (i=n)and(num+1>m)then exit(false);
                if num>m then exit(false);
             end;
        end;
        exit(true);
end;
procedure closef;
begin
        close(input);
        close(output);
end;
procedure main;
var
        a1,a2,a3:longint;
begin
        a1:=0;
        a2:=summ;
        while a1<a2 do
        begin
                a3:=(a1+a2)shr 1;
                if check(a3) then
                a2:=a3
                else a1:=a3+1;
        end;
        writeln(a1);
end;
begin
        init;
        main;
        closef;
end.