> var s:Array[1..2,0..11000] of int64;
>     n,m:longint;
>     f:array[0..11000] of longint;
>     bak:array[1..2,0..11000] of int64;
>     ss,tt,mid,ans:int64;
>   procedure init;
>   var i,j:longint;
>   begin
>    fillchar(s,sizeof(s),0);
>    readln(n,m);
>    for i:=1 to 2 do
>     for j:=1 to n do
>      begin
>       read(s[i,j]);
>       if s[i,j]>ss then ss:=s[i,j];
>       s[i,j]:=s[i,j-1]+s[i,j];
>      end;
>   end;
>   function ok(kk:int64):boolean;
>   var j,i,c,l1,l2:longint;
>   begin
>    ok:=false;
>    fillchar(f,sizeof(f),0); fillchar(bak,sizeof(bak),0);
>    l1:=0; l2:=0;
>    for i:=1 to n do
>     begin
>      while s[1,i]-s[1,l1]>kk do inc(l1);
>      while s[2,i]-s[2,l2]>kk do inc(l2);
>      bak[1,i]:=l1; bak[2,i]:=l2;
>      if (l1=i) or (l2=i) then exit;
>     end;
>    j:=0;
>    for i:=1 to n do
>     begin
>      c:=0; f[i]:=m+m;
>      l1:=i; l2:=i;
>      while s[1,i]+s[2,i]-s[1,j]-s[2,j]>kk do inc(j);
>      if f[i]>f[j]+1 then
>       f[i]:=f[j]+1;
>      while (l1+l2>0) do
>       begin
>        inc(c);
>        if l1>l2 then
>         l1:=bak[1,l1]
>        else
>         l2:=bak[2,l2];
>        if l1>l2 then
>         begin
>          if f[i]>f[l1]+c then
>           f[i]:=f[l1]+c;
>         end
>        else
>         begin
>          if f[i]>f[l2]+c then
>           f[i]:=f[l2]+c;
>         end;
>       end;
>      if f[i]>m then exit;
>     end;
>    ok:=(f[n]<=m);
>   end;
>   procedure print;
>   begin
>    writeln(ans);
>   end;
>   procedure work;
>   begin
>    tt:=s[1,n]+s[2,n];
>    while tt-ss>1 do
>     begin
>      mid:=(ss+tt) div 2;               
>      if ok(mid) then
>       tt:=mid
>      else
>       ss:=mid;
>     end;
>    mid:=ss;
>    while ok(mid)=false do inc(mid);
>    ans:=mid;
>   end;
> begin
>  init;
>  work;
>  print;
> end.
> 
> 

• e...原来是这样。。谢谢了。。。 (0) ylcx 2006-03-05 21:05:04