Cod sursa(job #25442)

Utilizator vanila0406Ionescu Victor vanila0406 Data 4 martie 2007 12:36:57
Problema Buline Scor 30
Compilator fpc Status done
Runda preONI 2007, Runda 3, Clasa a 9-a si gimnaziu Marime 2.54 kb
program buline;
var f,g:text;
        n,k:longint;
        v:array[0..400001] of integer;
        aux:array[0..400001] of int64;


procedure iofile;
var x,c,i:longint;
begin
        assign(f,'buline.in');
        reset(f);
        assign(g,'buline.out');
        rewrite(g);
        readln(f,n);
        aux[0]:=0;
        for i:=1 to n do
                begin
                        readln(f,x,c);


                        if c=0 then
                                begin
                                        aux[i]:=aux[i-1]-x;
                                        aux[n+i]:=-x;
                                        v[i]:=-x;
                                        v[n+i]:=-x;
                                end else
                                begin
                                        aux[i]:=aux[i-1]+x;
                                        aux[n+i]:=x;
                                        v[i]:=x;
                                        v[n+i]:=x;
                                end;
                end;
        for i:=n+1 to 2*n do
                aux[i]:=aux[i-1]+aux[i];
        k:=1;
end;


procedure prel;
var poz,p,u,sum:int64;
        max:longint;
        i:longint;
begin
        p:=1;
        u:=k;
        poz:=1;
        sum:=aux[k];
        max:=-maxlongint;
        for i:=k+1 to 2*n do
                begin
                        if poz+n-1<i then
                                begin
                                        sum:=sum-v[poz];
                                        inc(poz);
                                end;
                        if sum >max then
                                begin
                                        max:=sum;
                                        p:=poz;
                                        u:=i-1;
                                end;
                        sum:=sum+v[i];
                        if sum<aux[i]-aux[i-k] then
                                begin
                                        sum:=aux[i]-aux[i-k];
                                        poz:=i-k+1;
                                end;
                        if sum>max then
                                begin
                                        max:=sum;
                                        p:=poz;
                                        u:=i;
                                end;
                end;
        writeln(g,max,' ',p,' ',u-p+1);
        close(g);
end;


begin
        iofile;
        prel;
end.