PROGRAM SECVENTA2;    {INFOARENA}        {OK!  => a functionat din prima!}
(*
OBS!: Folosind metoda "Programarii Dinamice", algoritmul este foarte eficient
ca timp de executie, avand complexitatea de ordinul O(N).
*)
CONST NMAX=50000;
VAR S:ARRAY[0..NMAX] OF LONGINT;
    SM:ARRAY[0..NMAX] OF RECORD
                         S:LONGINT;
                         P:0..NMAX;
                         END;
    N,K,I,PSK,SSK,PMAX,FMAX,SMAX,X:LONGINT;
    F,G:TEXT;
(*
VARIABILE:
   - S[I]= suma elementelor din sir pana pe pozitia I;
   - SM[I]= secventa de suma maxima ce se termina pe pozitia I, avand:
                   >> S= suma secventei;
                   >> P= pozitia de inceput;
   - Secventa de suma maxima de lungime cel putin K, ce se termina pe
     pozitia curenta I, incepe pe pozitia PSK si are suma SSK.
   - Secventa de suma maxima de lungime cel putin K, care este solutia
     problemei, incepe pe pozitia PMAX, se termina pe pozitia FMAX si
     are suma maxima SMAX.
   - X= numarul de pe pozitia I din sir (numarul curent);
*)
BEGIN
ASSIGN(F,'secv2.in');
ASSIGN(G,'secv2.out');
RESET(F);
REWRITE(G);
READLN(F,N,K);
PMAX:=0;
FMAX:=0;
SMAX:=-MAXLONGINT;
S[0]:=0;
SM[0].P:=0;
SM[0].S:=0;
FOR I:=1 TO N DO
    BEGIN
    READ(F,X);
    S[I]:=S[I-1]+X;
    {Pas #1: Determin secventa de suma maxima ce se termina pe pozitia I.}
    IF (SM[I-1].S>0) THEN BEGIN
                          {Adaug elementul curent, X, la secventa maxima anterioara!}
                          SM[I].S:=SM[I-1].S+X;
                          SM[I].P:=SM[I-1].P;
                          END
                     ELSE BEGIN
                          {Incep cu X secventa maximala!}
                          SM[I].S:=X;
                          SM[I].P:=I;
                          END;
    {Pas #2: Determin secventa de suma maxima de lungime cel putin K,
             secventa ce se termina pe pozitia curenta I.}
    IF (I>=K) THEN
       BEGIN
       IF (SM[I-K].S>0) THEN BEGIN
                             {Se ia toata secventa incepand de pe pozitia
                              SM[I-K].P, pana pe pozitia curenta I.}
                             PSK:=SM[I-K].P;
                             SSK:=SM[I-K].S + (S[I]-S[I-K]);
                             END
                        ELSE BEGIN
                             {Se iua doar ultimele K elemente in secventa.}
                             PSK:=I-K+1;
                             SSK:=S[I]-S[I-K];
                             END;
       {Verific maximalitatea secventei.}
       IF (SSK>SMAX) THEN BEGIN
                          PMAX:=PSK;
                          FMAX:=I;
                          SMAX:=SSK;
                          END;
       END;
    END;
WRITE(G,PMAX,' ',FMAX,' ',SMAX);
CLOSE(F);
CLOSE(G);
END.