KAGAIN - Chiến trường Ô qua

Tác giả: ll931110

Ngôn ngữ: Pascal

Program KAGAIN;
        Const
                input  = '';
                output = '';
        Var
                  a,left,right,stack: array[1..30000] of longint;
                           t,n,i,top: longint;
                               fi,fo: text;

Procedure openfile;
          Begin
                Assign(fi, input);
                        Reset(fi);

                Assign(fo, output);
                        Rewrite(fo);
          End;

Procedure closefile;
          Begin
                Close(fo);
                Close(fi);
          End;

Procedure push(x: longint);
          Begin
                inc(top);
                stack[top]:= x;
          End;

Procedure solveleft;
          Var
                i: longint;
          Begin
                top:= 1;
                stack[top]:= 1;

                left[1]:= 1;
                For i:= 2 to n do
                        Begin
                                While (top > 0) and (a[stack[top]] >= a[i]) do dec(top);
                                If top = 0 then left[i]:= 1 else left[i]:= stack[top] + 1;

                                push(i);
                        End;
          End;

Procedure solveright;
          Var
                i: longint;
          Begin
                top:= 1;
                stack[top]:= n;

                right[n]:= n;
                For i:= n - 1 downto 1 do
                        Begin
                                While (top > 0) and (a[stack[top]] >= a[i]) do dec(top);
                                If top = 0 then right[i]:= n else right[i]:= stack[top] - 1;

                                push(i);
                        End;
          End;

Procedure solve;
          Var
                kq,i,x,y: longint;
          Begin
                Readln(fi, n);
                For i:= 1 to n do read(fi, a[i]);
                Readln(fi);

                solveleft;
                solveright;

                x:= left[1];
                y:= right[1];
                kq:= (y - x + 1) * a[1];

                For i:= 2 to n do
                        if kq < (right[i] - left[i] + 1) * a[i] then
                                Begin
                                        kq:= (right[i] - left[i] + 1) * a[i];
                                        x:= left[i];
                                        y:= right[i];
                                End;

                Writeln(fo, kq, ' ', x, ' ', y);
          End;

Begin
        openfile;
                Readln(fi, t);
                For i:= 1 to t do solve;

        closefile;
End.

Download