比赛 2008haoi模拟训练3 评测结果 AAAWAAWAAW
题目名称 阶梯教室设备利用 最终得分 70
用户昵称 thegy 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2008-04-24 10:19:57
显示代码纯文本
program rez;
var
  fin,fout:text;
  n,i,p,te:longint;
  be,en:array[1..10000]of longint;
  f:array[0..30000]of longint;
procedure qsort(l, r: Integer);
var
  i, j, x, y: integer;
begin
  i := l; j := r; x := en[(l+r) DIV 2];
  repeat
    while en[i] < x do i := i + 1;
    while x < en[j] do j := j - 1;
    if i <= j then
    begin
      y := en[i]; en[i] := en[j]; en[j] := y;
      y := be[i]; be[i] := be[j]; be[j] := y;
      i := i + 1; j := j - 1;
    end;
  until i > j;
  if l < j then qsort(l, j);
  if i < r then qsort(i, r);
end;
function max(x,y:longint):longint;
begin
  if x>y then max:=x
  else max:=y;
end;
begin
  assign(fin,'rez.in'); reset(fin);
  assign(fout,'rez.out'); rewrite(fout);
  read(fin,n);
  for i:=1 to n do
    read(fin,be[i],en[i]);
  qsort(1,n);
  te:=en[n];
  p:=1;
  f[0]:=0;
  for i:=1 to te do
  begin
    if i=en[p] then
    begin
      f[i]:=max(f[i-1],f[be[p]]+en[p]-be[p]);
      inc(p);
    end
    else
    begin
      f[i]:=f[i-1];
    end;
  end;
  writeln(fout,f[te]);
  close(fout);
end.