NKSEQ - Dãy số

Tác giả: ll931110

Ngôn ngữ: Pascal

Program NKSEQ;
        Const
                 input  = '';
                 output = '';
                    max = 100000;
        Type
                arr = array[1..max] of longint;
        Var
              a,l,rmin,rmax,left,right: arr;
                                     n: longint;

Procedure init;
          Var
                f: text;
                i: longint;
          Begin
                Assign(f, input);
                        Reset(f);
                                Readln(f, n);
                                For i:= 1 to n do read(f, a[i]);
                Close(f);
          End;

Procedure solve;
          Var
                      f: text;
                  i,num: longint;
          Begin
                left[1]:= a[1];
                For i:= 2 to n do left[i]:= left[i - 1] + a[i];

                right[n]:= a[n];
                For i:= n - 1 downto 1 do right[i]:= right[i + 1] + a[i];

                l[1]:= left[1];
                For i:= 2 to n do
                  if left[i] < l[i - 1] then l[i]:= left[i] else l[i]:= l[i - 1];

                rmin[n]:= right[n];
                For i:= n - 1 downto 1 do
                  if right[i] < rmin[i + 1] then rmin[i]:= right[i]
                                            else rmin[i]:= rmin[i + 1];

                rmax[n]:= right[n];
                For i:= n - 1 downto 1 do
                  if right[i] > rmax[i + 1] then rmax[i]:= right[i]
                                            else rmax[i]:= rmax[i + 1];

                num:= 0;
                If (a[1] > 0) and (l[n] > 0) then inc(num);
                If (a[n] > 0) and (a[n] + l[n - 1] > 0) then inc(num);

                For i:= 2 to n - 1 do
                  if (a[i] > 0) and (right[i] - rmax[i + 1] > 0)
                                and (right[i] + l[i - 1] > 0) then inc(num);

                Assign(f, output);
                        Rewrite(f);
                        Writeln(f, num);
                Close(f);
          End;

Begin
        init;
        solve;
End.

Download