Cod sursa(job #31843)

Utilizator andrei_infoMirestean Andrei andrei_info Data 16 martie 2007 17:42:11
Problema Buline Scor 20
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.64 kb
//buline infoarena preoni 2007 runda 3
const nmax = 200000;
var a:array[1..2*nmax] of integer;
    start,max : array[1..2*nmax] of longint;
    n:longint;

procedure citire;
var i,x,y:longint;
begin
assign(input,'buline.in'); reset(input);
readln(n);
for i:=1 to n do
        begin
        readln(x,y);
        if y = 0 then a[i]:=-x
        else a[i]:=x;
        end;
for i:=1 to n-1 do
        a[n+i]:=a[i];
n:=2*n-1;
closE(input);
end;

procedure calc;
var i,mmax,pstart,poz:longint;
begin
max[1]:=a[1];
start[1]:=1;

for i:=2 to n do
        begin
        if (max[i-1] + a[i] > a[i])  then
                begin
                max[i]:=max[i-1]+a[i];
                start[i]:=start[i-1];
                if i-start[i] + 1 > (n+1) div 2 then
                        begin
                        max[i]:=max[i]-a[start[i]];
                        inc(start[i]);
                        if max[i] <= a[i] then
                                begin
                                start[i]:=i;
                                max[i]:=i;
                                end;

                        end;

                end
        else
                begin
                max[i]:=a[i];
                start[i]:=i;
                end;
        end;
poz:=1; pstart:=1; mmax:=max[1];
for i:=1 to n do
        if mmax < max[i] then
                begin
                mmax:=max[i];
                pstart:=start[i];
                poz:=i;
                end;
writeln(mmax,' ',pstart,' ',poz-pstart+1);
end;

begin
citire;
assign(output,'buline.out'); rewritE(output);
calc;
close(output);
end.