ac1075a.pas

来自「这是在网络上搜集到的在东京大学的ACM上面解决的一些题目的源码」· PAS 代码 · 共 36 行

program tju1075;
const
  maxn=300000;
var
  a:array[1..maxn]of longint;
  t,u,n,l1,l2,i,j,p,f,r,s,ans,x,y:longint;
begin
  read(t);
  for u:=1 to t do begin
    read(n,l1,l2);
    s:=0;
    for i:=1 to l1 do begin
      read(a[i]);inc(s,a[i]);
    end;
    ans:=s;j:=0;p:=0;f:=0;r:=0;
    for i:=l1+1 to n do begin
      read(a[i]);inc(s,a[i]);
      inc(j);inc(r);a[r]:=a[j];
      while (a[r]<=0) and ((r>f+2) or (r=f+2) and (a[r-1]>0)) do begin
        if a[r-1]>0 then x:=r-1 else x:=r-2;
        y:=a[r]+a[x];
        if (x=f+1) or (a[x-1]>0) then begin a[x]:=-j;r:=x+1;end else begin a[x-1]:=-j;r:=x;end;
        a[r]:=y;
      end;
      if (r=f+1) or (a[f+1]>0) then x:=f+1 else x:=f+2;
      if (a[x]<=0) or (p<i-l2) then begin
        dec(s,a[x]);
        if (r=f+1) or (a[f+1]>0) then inc(p) else p:=-a[f+1];
        f:=x;
      end;
      if s>ans then ans:=s;
    end;
    writeln(ans);
  end;
end.