最大連続長さがmを超えないサブシーケンスと
タイトルの大意
長さnのシーケンスを指定して、その中の長さがmを超えない連続した部分を取り出して、最大を求めます.
問題を解く
ans=max{sum[i]−sum[j−1]} (i)=j−1で、かつ1<=j−i+1<=m)は、O(N 2)の暴力が位置iの前のsum[j-1]の最小であればよく、すなわち、静的なクエリ区間最小(STテーブル/線分樹)であり、O(NlogN)に最適化されることが明らかである.単調なキューのメンテナンスはO(N)に最適化します.
長さnのシーケンスを指定して、その中の長さがmを超えない連続した部分を取り出して、最大を求めます.
問題を解く
ans=max{sum[i]−sum[j−1]} (i)=j−1で、かつ1<=j−i+1<=m)は、O(N 2)の暴力が位置iの前のsum[j-1]の最小であればよく、すなわち、静的なクエリ区間最小(STテーブル/線分樹)であり、O(NlogN)に最適化されることが明らかである.単調なキューのメンテナンスはO(N)に最適化します.
const
maxn=200005;
var
x,sum:array[0..maxn]of longint;
w:array[0..4*maxn,1..3]of longint;
i,j,k:longint;
n,m,ans:longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
function min(a,b:longint):longint;
begin
if athen exit(a) else exit(b);
end;
procedure build(a,l,r:longint);
var mid:longint;
begin
w[a,1]:=l; w[a,2]:=r; w[a,3]:=0;
if l=r then begin w[a,3]:=sum[l]; exit; end;
mid:=(l+r)>>1;
build(a<<1,l,mid); build(a<<1+1,mid+1,r);
w[a,3]:=min(w[a<<1,3],w[a<<1+1,3]);
end;
function query(a,l,r:longint):longint;
var mid:longint;
begin
if (w[a,1]=l)and(w[a,2]=r) then exit(w[a,3]);
mid:=(w[a,1]+w[a,2])>>1;
if r<=mid then exit(query(a<<1,l,r)) else
if l>mid then exit(query(a<<1+1,l,r))
else exit(min(query(a<<1,l,mid),query(a<<1+1,mid+1,r)));
end;
begin
readln(n,m);
for i:=1 to n do
begin
read(x[i]); sum[i]:=sum[i-1]+x[i];
end;
build(1,1,n);
ans:=0;
for i:=n downto 2 do
begin
if i-m>0
then ans:=max(sum[i]-query(1,i-m,i-1),ans)
else ans:=max(sum[i]-query(1,1,i-1),ans);
end;
ans:=max(ans,x[1]);
writeln(ans);
end.