Pagini recente » Cod sursa (job #1635337) | Cod sursa (job #1706586) | Cod sursa (job #781772) | Monitorul de evaluare | Cod sursa (job #769668)
Cod sursa(job #769668)
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.