Cod sursa(job #769668)

Utilizator ctlin04UAIC.VlasCatalin ctlin04 Data 20 iulie 2012 14:40:59
Problema Buline Scor 100
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.46 kb
Program buline;
 type tip=record
          val,pos:longint;
          end;
var s,a:array [0..400000] of longint;
    deq:array [0..100000] of tip;
    i,n,x,cap,coada,max,st,l,op:longint;
    fi,fo:text;
begin
 assign(fi,'buline.in');
  assign(fo,'buline.out');
 reset(fi); rewrite(fo); readln(fi,n);
  for i:=1 to n do begin
                    readln(fi,a[i],op);
                    if op=0 then a[i]:=-a[i];
                    s[i]:=a[i]+s[i-1];
                    s[i+n]:=a[i];
                    end;
  for i:=n+1 to 2*n-1 do s[i]:=s[i]+s[i-1];
   cap:=1; coada:=1; deq[1].val:=s[1]; deq[1].pos:=1; max:=s[1]; l:=1; st:=1;
  for i:=2 to 2*n-1 do begin
                   if s[i]>deq[coada].val then begin inc(coada); deq[coada].val:=s[i]; deq[coada].pos:=i; end
                    else begin
                          while (s[i]<=deq[coada].val) and (coada>=cap) do dec(coada);
                           inc(coada);
                          deq[coada].val:=s[i]; deq[coada].pos:=i;
                          end;
                   if deq[cap].pos<i-n then inc(cap);
                   if s[i]-deq[cap].val>max then begin
                                             max:=s[i]-deq[cap].val;
                                             st:=deq[cap].pos+1;
                                             l:=i-deq[cap].pos;
                                             end;
                    end;
 write(fo,max,' ',st,' ',l);
 close(fo);
end.