jzoj 1146. 危険係数(acrobat)

1146.危険係数(acrobat):input:acrobat.in output:acrobat.out
時間制限:
1000 msのスペース制限:
262144 KB具体的な制限
Goto ProblemSet
タイトルの説明
N(1<=N<=50000、1..Nと表記)個人は畳羅漢雑技を計画し、一番下の人を除いて誰もが別の人の頭の上に立っている.誰もが自分の体重を持っていますW_i(1<=W_i<=10000)とパワーS_i(1<=S_i<=1億円)は、一人当たりの危険係数を、彼が受けた重量(注意:彼自身を除く)から彼の力を差し引いた差として定義し、N人の中で最大の危険係数を最小にする順序を見つけるのが任務です.
入力
1行目:整数Nを入力します.
2行目からN+1行目:i+1行目はi人目の体重と力を記述し、中間はスペースで区切られている.
しゅつりょく
最適順序で最大の危険係数を表す整数を出力します.
サンプル入力

3
10 3
2 5
3 3

サンプル出力

2

データ範囲の制限
欲張りは、最良を達成するためには、下の人ほど力と体重をできるだけ大きくしなければならないので、体重と力の和をキーワードに並べ替えて、
そしてそのまま解くといいです.
コードは次のとおりです.

var
 a,b,c:array[1..50000]of longint;
 n,max:longint;

procedure init;
var i:longint;
begin
 readln(n);
 for i:=1 to n do
  begin
   readln(a[i],b[i]);
   c[i]:=a[i]+b[i];
  end;
end;

procedure qsort(l,r:longint);
var i,j,k,m:longint;
begin
 if l>=r then exit;
 i:=l; j:=r; k:=c[(i+j) div 2];
 repeat
  while c[i]do inc(i);
  while c[j]>k do dec(j);
  if i<=j then
   begin
    m:=c[i]; c[i]:=c[j]; c[j]:=m;
    m:=a[i]; a[i]:=a[j]; a[j]:=m;
    m:=b[i]; b[i]:=b[j]; b[j]:=m;
    inc(i); dec(j);
   end;
  until i>j;
 qsort(l,j);
 qsort(i,r);
end;

procedure main;
var i,k,j:longint;
begin
 k:=0;
 max:=-maxlongint;
 for i:=1 to n do
  begin
    if k-b[i]>max then max:=k-b[i];
    k:=k+a[i];
  end;
 write(max);
end;

begin
 assign(input,'acrobat.in');reset(input);
 assign(output,'acrobat.out');rewrite(output);
 init;
 qsort(1,n);
 main;
 close(input); close(output);
end.