ac1071.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1071;
const
  maxn=200000;
var
  sum:array[0..maxn]of int64;
  heap:array[1..maxn]of longint;
  t,u,n,l1,l2,i,h,x:longint;
  ans,tmp:int64;
procedure ins(x:longint);
  var
    p,q:longint;
  begin
    inc(h);p:=h;
    while p>1 do begin
      q:=p shr 1;
      if sum[x]>=sum[heap[q]] then break;
      heap[p]:=heap[q];p:=q;
    end;
    heap[p]:=x;
  end;
procedure del;
  var
    p,l,r:longint;
  begin
    p:=1;
    repeat
      l:=p*2;r:=l+1;
      if (r<h) and (sum[heap[h]]>sum[heap[r]]) and (sum[heap[r]]<sum[heap[l]]) then begin
        heap[p]:=heap[r];p:=r;
      end
      else if (l<h) and (sum[heap[h]]>sum[heap[l]]) then begin
        heap[p]:=heap[l];p:=l;
      end
      else break;
    until false;
    heap[p]:=heap[h];dec(h);
  end;
begin
  read(t);
  for u:=1 to t do begin
    read(n,l1,l2);
    ans:=maxlongint;ans:=-ans*ans;
    sum[0]:=0;h:=0;
    for i:=1 to n do begin
      read(x);
      sum[i]:=sum[i-1]+x;
      while (h>0) and (i-heap[1]>l2) do del;
      if i>=l1 then ins(i-l1);
      if h>0 then begin
        tmp:=sum[i]-sum[heap[1]];
        if tmp>ans then ans:=tmp;
      end;
    end;
    writeln(ans);
  end;
end.