ac1167.pas

某牛人写的acm.tongji.edu.cn上大部分ac的代码,仅供学习研究,请不要用来作弊

program tju1167;
{$Q-,R-}
const
  maxn=10000;
  maxm=6001;
  imp=-2100000000;
var
  a:array[boolean,1..maxn]of longint;
  f:array[boolean,0..maxm]of longint;
  n,m,i,j,ans,k,l,t:longint;
  b1,b2:boolean;
begin
  repeat
    read(n,m);m:=m*2+1;
    for i:=1 to n do read(a[true,i]);
    for i:=1 to n do begin read(a[false,i]);inc(a[true,i],a[false,i]);end;

    ans:=imp;f[false,0]:=0;f[false,1]:=imp;
    for i:=1 to n do begin
      b1:=odd(i);b2:=not b1;
      k:=i-n+m;if k<1 then k:=1;
      if i<m then l:=i else l:=m;
      for j:=l downto k do begin
        if f[b2,j-1]>f[b2,j] then f[b2,j]:=f[b2,j-1];
        f[b1,j]:=f[b2,j]+a[odd(j),i];
      end;
      if l<m then f[b1,l+1]:=imp else if f[b1,m]>ans then ans:=f[b1,m];
    end;
    writeln(ans);
  until seekeof;
end.