Cod sursa(job #26852)

Utilizator fogabFodor Gabor fogab Data 5 martie 2007 21:56:16
Problema Buline Scor 100
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.26 kb
 var f:text;
    a:array[1..200000] of integer;
    t,h,g:array[0..200000] of longint;
    max,cmax,s,cs,l,cl,n,i,j,help:longint;

begin
h[0]:=0;
t[0]:=0;
assign(f,'buline.in');
reset(f);
readln(f,n);
for i:=1 to n do begin
   read(f,a[i],j);
   if j=0 then a[i]:=-a[i];
   h[i]:=h[i-1]+a[i];
   if h[i]>t[i-1] then begin
                       t[i]:=h[i];
                       g[i]:=i;
                       end
      else begin
           t[i]:=t[i-1];
           g[i]:=g[i-1];
           end;
   end;
close(f);

max:=a[1];
cmax:=max;
l:=1;
cl:=1;
s:=1;
cs:=1;
for i:=2 to n do
  begin
    if cmax<=0 then begin
                    cmax:=a[i];
                    cl:=1;
                    cs:=i;
                    end
    else begin
         cmax:=cmax+a[i];
         inc(cl);
         end;
    if (max<cmax) then begin
                       max:=cmax;
                       s:=cs;
                       l:=cl;
                       end;
    help:=t[i-1]+h[n]-h[i-1];
    if (help>max) then begin
                       max:=help;
                       s:=i;
                       l:=n-i+1+g[i-1];
                       end;
  end;
assign(f,'buline.out');
rewrite(f);
writeln(f,max,' ',s,' ',l);
close(f);
end.