Cod sursa(job #26453)

Utilizator CezarMocanCezar Mocan CezarMocan Data 5 martie 2007 16:58:20
Problema Buline Scor 90
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.7 kb
var v,x,s,t:array[0..400010]of longint;
    i,smax,sc,p,su,j,l,n,b,c,pmax,lmax,max,poz,lung:longint;
begin
assign(input,'buline.in');reset(input);
assign(output,'buline.out');rewrite(output);
readln(n);
for i:=1 to n do
        begin
        readln(b,c);
        if c=1 then
                v[i]:=b
        else
                v[i]:=-b;
        v[n+i]:=v[i];
        end;
sc:=v[1];
smax:=v[1];
p:=1;l:=1;
for i:=2 to 2*n do
        begin
        if l<n then
        if sc+v[i]>v[i]
                then begin
                sc:=sc+v[i];
                inc(l);
                end
        else
                begin
                sc:=v[i];
                p:=i;
                l:=1;
                end;
        if sc>smax then
                begin
                smax:=sc;
                pmax:=p;
                lmax:=l;
                end;
        end;
s[1]:=v[1];
for i:=2 to n do
        s[i]:=s[i-1]+v[i];
t[1]:=s[1];
for i:=2 to n do
        begin
        t[i]:=t[i-1];
        if s[i]>t[i] then
                t[i]:=s[i];
        end;
max:=0;poz:=0;lung:=0;
for i:=1 to n do
        begin
        if t[i-1]+s[n]-s[i-1]>max then
                begin
                max:=t[i-1]+s[n]-s[i-1];
                j:=i;
                lung:=0;
                su:=v[i];
                while su<>max do
                        begin
                        inc(j);
                        su:=su+v[j];
                        inc(lung);
                        end;
                poz:=i;
                end;
        end;
if max>smax then
        writeln(max,' ',poz,' ',lung+1)
else
        writeln(smax,' ',pmax,' ',lmax);
close(input);close(output);
end.