1115. The Energy You Have to Start With

Task i SPENDS cost energy and can only be begun when you are holding at least need energy, where need is never less than cost. Every task must be done, in an order you choose.

Print the smallest amount of energy you can start with.

tasks (cost=1,need=3) (cost=2,need=4) (cost=10,need=11) -> 14 tasks (cost=5,need=5) -> 5 tasks (cost=1,need=1) (cost=2,need=2) (cost=3,need=3) -> 6 tasks (cost=1,need=100) (cost=100,need=101) -> 102

Trace the first line. Sort by cost - need, which is -2, -2 and -1, so the ten-cost task goes LAST. Starting with 14: the first task needs 3 and 14 is enough, leaving 13. The second needs 4, leaving 11. The third needs 11, and 11 is exactly enough. Starting with 13 fails at the last step.

## What most people try first

Sorting by need descending, so that the most demanding task is met while you are richest. That is close and it is wrong. On (1,100) (100,101) it puts (100,101) first, requiring 101 at the start and then 1 left over against a need of 100, so it demands 200. The right order puts (1,100) first, requiring 100, then 99 against a need of 101, so 102 overall.

Sorting by cost descending is wrong for the same reason in reverse.

Trying every order costs n!.

## The method

sort by (cost - need) ASCENDING spent = 0 answer = 0 for (cost, need) in that order: answer = max(answer, spent + need) spent = spent + cost

One sort and one pass.

The formula inside the loop is worth stating separately. If you start with E and run the tasks in a fixed order, the jth task is begun holding E - (the costs of everything before it), and that must be at least need_j. So E must be at least need_j plus the costs before j, for every j, and the smallest valid E is the largest of those.

## Why the difference is the right key

Take any order and two ADJACENT tasks, a immediately before b, with S spent before them. Everything outside the pair is unaffected by a swap, because the pair spends cost_a + cost_b either way.

The requirement contributed by the pair is

a then b: max( S + need_a , S + cost_a + need_b ) b then a: max( S + need_b , S + cost_b + need_a )

Subtracting S and then need_a + need_b from both sides of the comparison turns it into

max( -need_b , cost_a - need_a ) against max( -need_a , cost_b - need_b )

Since cost <= need, both cost_a - need_a and cost_b - need_b are at most 0, while -need_a and -need_b are also at most 0, and the comparison reduces to cost_a - need_a against cost_b - need_b whenever those dominate, which is the interesting case. Putting a first is therefore at least as good when cost_a - need_a <= cost_b - need_b.

An order unimprovable by adjacent swaps is exactly the one sorted by cost - need ascending, and since adjacent swaps connect every order to every other, that order is optimal.

A shorter way to see the same thing: need - cost is the energy the task takes and does not give back beyond its own spending, so the tasks with the biggest such shortfall should be done while the most energy is still in hand.

## The boundary that breaks a careless implementation

The running maximum is taken BEFORE the cost is subtracted, because the requirement is checked at the moment the task begins, not after it finishes. Swapping those two lines understates the answer by the last task's cost.

Tasks with cost == need are legal and contribute nothing beyond their own cost, and a task with cost = 0 and need = 5 still forces 5 into the answer.

## Sizes

n reaches 2 * 10^5 and both numbers reach 10^9, so the total spent reaches 2 * 10^14 and so does the answer. That is far past the 2147483647 limit of a signed 32-bit integer, and three tasks of 10^9 already demand 3 * 10^9, which the eighth test checks.

## A related problem

Problem #1113 also sorts by a difference of two costs, but there the difference decides which SIDE a person goes to under a quota, and here it decides the ORDER. The same algebraic move serves two different questions, which is why they sit in the same block.

Constraints - `1 ≤ n ≤ 200000` - `0 ≤ cost ≤ need ≤ 1000000000`