KAGAIN - Chiến trường Ô qua

Tác giả: ladpro98

Ngôn ngữ: Pascal

program kagain;
uses    math;
const   fi='';
        fo='';
var     a:array[0..30001] of longint;
        left,right:array[0..30001] of longint;
        area,dau,cuoi,n,t,i,j:longint;
        inp,oup:text;
procedure openFile;
begin
        assign(inp,fi);
        reset(inp);
        assign(oup,fo);
        rewrite(oup);
end;

procedure closeFile;
begin
        close(inp);
        close(oup);
end;

procedure process;
var     i,t:longint;
begin
        area:=0;
        for i:=1 to n do
        begin
                left[i]:=0;
                right[i]:=0;
        end;
        left[1]:=0;
        for i:=2 to n do
        begin
                t:=i-1;
                while a[t]>=a[i] do
                        t:=left[t];
                left[i]:=t;

        end;

        right[n]:=n+1;
        for i:=n-1 downto 1 do
        begin
                t:=i+1;
                while a[t]>=a[i] do
                        t:=right[t];
                right[i]:=t;

        end;

        for i:=1 to n do
        begin
                if area<((right[i]-left[i]-1)*a[i]) then
                begin
                        area:=(right[i]-left[i]-1)*a[i];
                        dau:=left[i]+1;
                        cuoi:=right[i]-1;
                end;
        end;
end;

begin
        openFile;
        readln(inp,t);
        for i:=1 to t do
        begin
                readln(inp,n);
                for j:=1 to n do read(inp,a[j]);
                process;
                writeln(oup,area,' ',dau,' ',cuoi);
        end;
        close(oup);
end.

Download