Cow Acrobats (PKU 3045)

http://acm.pku.edu.cn/JudgeOnline/problem?id=3045

問題

牛たちN頭が縦に乗っていく。各牛の重さがWi,強さがSiで与えられたとき、その牛が崩れるリスクはその牛の上に乗っている全ての牛の重さの合計からその牛の強さを引いた物である。牛を最適に並べるとリスクの最大値の最小値はいくらになるか。
1<=N<=50000
1<=Wi<=10000
1<=Si<=1000000000

解法

Wi+Siの低い牛ほど上に乗るようにすれば良い。