1117. Standing on Each Other's Shoulders

n acrobats build one tower, each standing on the shoulders of the one below. Acrobat i weighs w and can bear s.

The STRAIN on an acrobat is the total weight of everyone standing above them minus their own strength. The strain may be negative, which simply means they are comfortable.

Order the acrobats so that the LARGEST strain in the tower is as small as possible, and print that value.

acrobats (w=1,s=2) (w=3,s=4) (w=5,s=6) -> -2 acrobats (w=5,s=3) -> -3 acrobats (w=10,s=0) x 3 -> 20 acrobats (w=1,s=100) (w=100,s=1) (w=50,s=50) -> 50

Trace the first line. Sort by w + s descending: the sums are 3, 7 and 11, so the order from the BOTTOM up is (5,6), (3,4), (1,2). The top acrobat carries nothing, so their strain is 0 - 2 = -2. The middle one carries 1, so 1 - 4 = -3. The bottom one carries 4, so 4 - 6 = -2. The largest is -2.

## What most people try first

Putting the STRONGEST acrobat at the bottom. That ignores that the strongest one is also part of the load for everybody below them. On (1,100) (100,1) (50,50) the strongest is (1,100), and putting them at the bottom gives, from the bottom up, (1,100), then the other two in some order: (100,1) carrying 50 gives strain 49, (50,50) carrying 0 gives -50, and (1,100) carrying 150 gives 50. The answer is 50, which happens to be right here. Putting the HEAVIEST at the bottom is the other instinct, and on (6,3) (2,7) (8,1) (4,4) (1,9) heaviest-first gives a largest strain of 12 where 11 is achievable.

Trying every order costs n!.

## The method

sort by (w + s) DESCENDING; that is the order from the BOTTOM of the tower upward above = 0 worst = minus infinity walk the sorted list from the END (the top) towards the start: worst = max(worst, above - s) above = above + w

One sort and one pass.

## Why weight plus strength is the key

Take any order and two ADJACENT acrobats, a directly above b, with A the total weight of everybody above a. Everything outside the pair is untouched by a swap, because the pair contributes w_a + w_b to everyone below it either way, and the pair carries the same A from above.

The strains of the pair are

a above b: a has A - s_a, b has A + w_a - s_b b above a: b has A - s_b, a has A + w_b - s_a

A - s_a is smaller than A + w_b - s_a and A - s_b is smaller than A + w_a - s_b, so each maximum is decided by the second term of its own arrangement. Putting a above b is therefore at least as good exactly when

A + w_a - s_b <= A + w_b - s_a

which rearranges to w_a + s_a <= w_b + s_b. So the acrobat with the SMALLER weight plus strength belongs higher up, and the one with the larger sum belongs lower down.

An order unimprovable by adjacent swaps is precisely the one sorted by w + s, so that order is optimal.

## Why the comparator is a total order

The key is a single number, w + s, so the comparison is an ordinary numeric one: total, transitive, and safe to hand to any sort. That is worth pointing out because the pairwise derivation above LOOKS like it might produce a two-sided comparison, as problem #1111's does, and it does not. Whenever a pairwise exchange rearranges into "one number per item", the sort is trivially valid; when it does not, as in #1111, the grouping has to be done by hand.

## The boundary that breaks a careless implementation

The answer can be NEGATIVE, and usually is when the acrobats are strong. Starting the running maximum at 0 reports 0 for the first example instead of -2.

The top acrobat carries nothing, so their load is 0, not their own weight. Walking from the bottom and accumulating weight as you go gets that wrong by one acrobat.

## Sizes

n reaches 2 * 10^5 and both numbers reach 10^9, so the weight above someone reaches 2 * 10^14 and the strain reaches the same magnitude. That is far past the 2147483647 limit of a signed 32-bit integer. Four acrobats of 10^9 with no strength already give 3 * 10^9, which the last test checks.

## A related problem

Problem #1110 is the other problem in this block whose comparator comes out of an adjacent swap and collapses to a single sort key. Reading the two derivations together is the fastest way to learn the move: write the two orderings, cancel everything common, and read the key off what is left.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ w ≤ 1000000000` - `0 ≤ s ≤ 1000000000`