比赛 20110729 评测结果 AAAAAAAAAAAA
题目名称 最后的利益 最终得分 100
用户昵称 老虎小飞 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2011-07-29 12:11:20
显示代码纯文本
var
f,l:array[0..11000]of longint;
a,w:array[0..22000]of longint;
n,x,y,i,ans:longint;

function max(a,b:longint):longint;
begin
    if a>b then  exit(a);
    exit(b);
end;

procedure kp(l,r:longint);
var
t,m,i,j,m0:longint;
begin
    i:=l;j:=r;m:=a[(i+j) div 2];m0:=w[(i+j) div 2];
    repeat
        while (a[i]<m)or((a[i]=m)and(w[i]<0)and(m0>0)) do inc(i);
        while (a[j]>m)or((a[j]=m)and(w[j]>0)and(m0<0)) do dec(j);
        if i<=j then begin
            t:=a[i];a[i]:=a[j];a[j]:=t;
            t:=w[i];w[i]:=w[j];w[j]:=t;
            inc(i);dec(j);
        end;
    until i>j;
    if (i<r) then kp(i,r);
    if (l<j) then kp(l,j);
end;

begin
    assign(input,'9cwy.in');reset(input);
    assign(output,'9cwy.out');rewrite(output);
    read(n);
    for i:=1 to n do begin
        read(a[i],a[i+n]);
        w[i]:=i;w[i+n]:=-i;
        l[i]:=a[i+n]-a[i];
    end;
    kp(1,n*2);
    for i:=1 to n*2 do begin
        if w[i]>0 then begin
            f[w[i]]:=ans;
        end
        else begin
            ans:=max(ans,f[-w[i]]+l[-w[i]]);
        end;
    end;
    writeln(ans);
    close(input);close(output);
end.