Cod sursa(job #591973)

Utilizator rudarelLup Ionut rudarel Data 26 mai 2011 09:32:29
Problema Secventa 2 Scor 100
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.05 kb


program secventa2;

const mic = -1500000000;
      mare = 1500000000;

var x,l,sum:array[0..50000] of longint;
    sumopt,sumcur,lcur,n,k,pozi,pozf,max,min,i,q,s,poz,j,ind,nr:longint;

procedure load;
var f:Text;
begin
assign(f,'secv2.in'); reset(f);
readln(f,n,k);
for i:=1 to n do read(f,x[i]);
close(f);
end;

procedure solve;
begin
i:=1;
while i<=n do begin
max:=mic; s:=0; poz:=0;
 for j:=i to n do begin
  s:=s+x[j];
  if s > max then begin
        max:=s;
        poz:=j;
  end;
 end;
inc(nr); l[nr]:=poz-i+1; sum[nr]:=max; i:=poz+1;
end;

sumopt:=mic; i:=0; lcur:=1; sumcur:=0;
while i<=n-k do begin
dec(lcur); sumcur:=sumcur - x[i]; inc(i);
 while lcur < k do begin
  inc(ind);
  lcur:=lcur + l[ind];
  sumcur:=sumcur+sum[ind];
 end;

if sumcur > sumopt then begin
        sumopt:=sumcur;
        pozi:=i;
        pozf:=i+lcur-1;
end;
end;

end;

procedure save;
var g:text;
begin
assign(g,'secv2.out'); rewrite(g);
writeln(g,pozi, ' ',pozf, ' ',sumopt);
close(G);
end;

begin
load;
solve;
save;
end.