记录编号	15382	评测结果	AAAAAAAAAA
题目名称	166.[USACO Mar07] 平衡的阵容	最终得分	100
用户昵称	tyn1993	是否通过	通过
代码语言	Pascal	运行时间	0.195 s
提交时间	2009-11-12 17:06:56	内存使用	1.16 MiB

program tyn;
type
  cow=record
    zz,zb:longint;
  end;
var
  cows:array[0..50001] of cow;
  sum:array[0..50001] of longint;
  h:array[-50001..50001] of longint;
  mark:array[-50001..50001] of boolean;
  n,max,i,t:longint;
procedure qsort(l,r:longint);
var
  x,y,mid:longint;
begin
  x:=l;
  y:=r;
  mid:=cows[(l+r) div 2].zb;
  repeat
    while cows[x].zb<mid do inc(x);
    while cows[y].zb>mid do dec(y);
    if x<=y then
    begin
      cows[0]:=cows[x];
      cows[x]:=cows[y];
      cows[y]:=cows[0];
      inc(x);
      dec(y);
    end;
  until x>y;
  if l<y then qsort(l,y);
  if r>x then qsort(x,r);
end;
begin
  assign(input,'balance.in');
  reset(input);
  assign(output,'balance.out');
  rewrite(output);
  fillchar(cows,sizeof(cows),0);
  fillchar(h,sizeof(h),0);
  fillchar(sum,sizeof(sum),0);
  fillchar(mark,sizeof(mark),false);
  readln(n);
  mark[0]:=true;
  for i:=1 to n do
  begin
    readln(cows[i].zz,cows[i].zb);
    if cows[i].zz=0 then cows[i].zz:=-1;
  end;
  qsort(1,n);
  for i:=1 to n do
  begin
    sum[i]:=sum[i-1]+cows[i].zz;
    if not mark[sum[i]] then
    begin
      mark[sum[i]]:=true;
      h[sum[i]]:=i;
    end;
  end;
  max:=0;
  for i:=1 to n do
  begin
    t:=h[sum[i]];
    if i>=t+1 then
      if cows[i].zb-cows[t+1].zb>max then
        max:=cows[i].zb-cows[t+1].zb;
  end;
  writeln(max);
  close(input);
  close(output);
end.