hackercupai/hackercup huggingface dataset:
We can observe that any combined timber interval must consist of 0 or more trees falling to the right followed by 0 or more trees falling to the left (with these two sequences of trees meeting at a common point in between).

Let \(R_p\) be the maximum length of a combined timber interval whose right endpoint is \(p\) and which consists only of trees cut down to the right. Let \(L_p\) similarly be the maximum length of a combined timber interval whose left endpoint is \(p\) and which consists only of trees cut down to the left. The answer (the maximum length of any combined timber interval) is then the maximum of \(( R_p + L_p )\) over all possible choices of \(p\).

What remains is computing these \(R\) and \(L\) values. We'll consider only the \(R\) values for now, with the \(L\) values computed in a very similar fashion (imagine that the trees are reversed on the number line, such that the \(i\)th tree is at position \(-P_i\) rather than \(P_i\)).

We'll use a dynamic programming approach, initially assuming that \(R_p = 0\) for each \(p\) and then increasing the \(R\) values as much as possible until we've considered all possible ways of increasing them. We'll first sort the trees in increasing order of position, and then iterate over them in that order. For the \(i\)th tree, a sequence of right-falling trees ending at position \(P_i\) may have that tree added onto it, meaning that we must have \(R_{P_i+H_i} \geq R_{P_i} + H_i\), and should therefore set \(R_{P_i+H_i} := max ( R_{P_i+H_i}, R_{P_i} + H_i )\).

Note that, though \(R_p\) is defined and possibly relevant for any integer \(p\) in [\(-10^9, 10^9\)], at most \(N\) entries are non-zero (at most one for each tree). Therefore, in order to keep memory usage manageable, we should store a sparse mapping of \(p \rightarrow R_p\), for example using a hash table (such as a C++ `unordered_map` or Python `dict`). This can also help with efficient computation of \(max_p ( R_p + L_p )\), as we should only consider positions \(p\) for which either \(R_p\) or \(L_p\) is non-zero.

The time complexity of this algorithm is \(O(N \log(N))\), resulting from sorting the trees.