Cod sursa(job #26116)

Utilizator vladcyb1Vlad Berteanu vladcyb1 Data 5 martie 2007 10:55:50
Problema Buline Scor 100
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.2 kb

 const
      FIN = 'buline.in';
      FOUT = 'buline.out';
      NMAX = 400000;

 var
    f, g : text;
    A, DEQ : array[ 0..NMAX ] of longint;
    i, j, N, first, last, y, smax, lmax, pmax : longint;

 begin
   assign( f, FIN ); reset( f ); readln( f, N );
   for i := 1 to N do
    begin
     readln( f, A[i], y );
     if y = 0 then A[i] := - A[i];
    end;
   for i := N + 1 to 2 * N do A[i] := A[ i - N ];
   for i := 1 to 2 * N do A[i] := A[i-1] + A[i];
   first := 1; last := 1; DEQ[1] := 0; Smax := - maxlongint;
   for i := 1 to 2 * N do
     begin
       // extragere deque
       while ( first <= last ) and ( i - DEQ[first] > N ) do inc( first );
       if A[i] - A[ DEQ[first ] ] > Smax then begin Smax := A[i] - A[ Deq[first] ];
                                                    pmax := Deq[first] + 1;
                                                    lmax := i - Deq[first];
                                              end;
        // inserare deque
        while ( last >= first ) and ( A[Deq[last]] > A[i] ) do dec( last );
        inc( last ); Deq[last] := i;
     end;

   assign( g, FOUT ); rewrite( g ); writeln( g, smax,' ',pmax,' ',lmax ); close(  g );
  end.