那么我们要求的就是找出一种牛的排列方式，令max(w1+⋅⋅⋅+wi−1−si)max(w1+···+wi−1−s)小，记这个值为valval。

为了求排序的方案，可以交换ii,i+1i+1牛的位置，看看满足什么等价条件，就可以使得交换之后valval不比之前大。

下面求交换之后valval不比之前大的等价条件：
（注意到交换ii,i+1i+1牛的位置不会影响其他牛的风险度，故只需考察这两头牛。）

交换前：
牛ii:
w1+⋅⋅⋅+wi−1−siw1+···+wi−1−si ①
牛i+1i+1:
w1+⋅⋅⋅+wi−1+wi−si+1w1+···+wi−1+wi−si+1 ②
交换后：
牛ii:
w1+⋅⋅⋅+wi−1+wi+1−siw1+···+wi−1+wi+1−si ③
牛i+1i+1:
w1+⋅⋅⋅+wi−1−si+1w1+···+wi−1−si+1 ④

valval不比之前大，即max(①,②)⩾max(③,④)max(①,②)⩾max(③,④)

下面的任务是求 max(①,②)⩾max(③,④)max(①,②)⩾max(③,④) 的等价条件：
注意到四个柿子式子都有w1+⋅⋅⋅+wi−1w1+···+wi−1，同时删去不影响结果，故等价于：

max(−si,wi−si+1)⩾max(wi+1−si,−si+1)
max(−si,wi−si+1)⩾max(wi+1−si,−si+1)
若−si>wi−si+1−si>wi−si+1 , 但−si[HTML_REMOVED]−si+1wi−si+1>−si+1
故上式进一步等价于：
wi−si+1⩾wi+1−si
wi−si+1⩾wi+1−si
即
wi+si⩾wi+1+si+1

C++代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 5e4 + 10;
struct sortt{
    int w,s;
}a[N];

bool cmp(struct sortt a, struct sortt b)
{
    return a.s + a.w < b.s + b.w;
}

int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i].w >> a[i].s;

    sort(a, a + n, cmp);

    int w_sum = a[0].w;
    int ans = 0 - a[0].s;

    for(int i = 1; i < n; i++)
    {
        if(w_sum - a[i].s > ans) ans = w_sum - a[i].s;
        w_sum += a[i].w;
    }

    cout << ans << endl;

    return 0;
}