比赛 20110729 评测结果 AAAAAAAAAAAA
题目名称 最后的利益 最终得分 100
用户昵称 reamb 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2011-07-29 09:30:18
显示代码纯文本
program zuihoudeliyi;
var
  left,right:array[0..10000]of longint;
  f:array[0..10000]of longint;
  n,i,j,d,max,p:longint;
procedure sort(l,r: longint);
      var
         i,j,x,y: longint;
      begin
         i:=l;
         j:=r;
         x:=left[(l+r) div 2];
         repeat
           while left[i]<x do
            inc(i);
           while x<left[j] do
            dec(j);
           if not(i>j) then
             begin
                y:=left[i];
                left[i]:=left[j];
                left[j]:=y;
                y:=right[i];
                right[i]:=right[j];
                right[j]:=y;
                inc(i);
                j:=j-1;
             end;
         until i>j;
         if l<j then
           sort(l,j);
         if i<r then
           sort(i,r);
      end;
begin
  assign (input,'9cwy.in');
  reset (input);
  assign (output,'9cwy.out');
  rewrite (output);
    readln (n);
    for i:=1 to n do
      readln (left[i],right[i]);
    right[0]:=0;
    left[0]:=0;
    sort(1,n);
    d:=0;
    for i:=1 to n do
    begin
      max:=0;
      p:=right[i]-left[i];
      for j:=i-1 downto 0 do
        if (left[i]>=right[j])and(f[j]+p>max) then
          max:=f[j]+p;
      f[i]:=max;
      if max>d then
        d:=max
    end;
    writeln (d);
  close (input);
  close (output)
end.