Flattening the Mountain

Let $C_i$ be the number of selected bombs whose intervals contain position $i$. After all selected bombs are used, position $i$ has height $0$ if and only if $C_i \geq A_i$. Thus, the task is to choose a minimum-cost subset of bombs satisfying every interval-covering lower bound.

Construct a minimum-cost flow graph with vertices $0,1,\ldots,N$.

• For every $i$ ($1 \leq i \leq N$), add an edge $i-1 \rightarrow i$ with capacity $M-A_i$ and cost $0$.
• For every bomb $j$, add an edge $L_j-1 \rightarrow R_j$ with capacity $1$ and cost $W_j$.

Send exactly $M$ units of flow from vertex $0$ to vertex $N$ at minimum cost. If some $A_i>M$, the instance is immediately impossible.

Consider the cut between vertices $0,1,\ldots,i-1$ and vertices $i,i+1,\ldots,N$. Every original edge goes from a smaller-numbered vertex to a larger-numbered vertex, so a flow of value $M$ crosses this cut by exactly $M$ units.

The edge $i-1 \rightarrow i$ can carry at most $M-A_i$ units. Therefore, at least $A_i$ units must cross the cut through bomb edges. A bomb edge $L_j-1 \rightarrow R_j$ crosses this cut exactly when $L_j \leq i \leq R_j$. Hence, the bomb edges used by the flow cover position $i$ at least $A_i$ times.

Conversely, suppose a feasible subset of bombs is selected. Assign a distinct flow path to each selected bomb. That path follows zero-cost edges from $0$ to $L_j-1$, takes the bomb edge $L_j-1 \rightarrow R_j$, and then follows zero-cost edges to $N$. Every remaining path uses only zero-cost edges.

The zero-cost edge at position $i$ is used by exactly $M-C_i$ paths. Since $C_i \geq A_i$, we have $M-C_i \leq M-A_i$, so every capacity constraint is satisfied. Thus, every feasible bomb subset corresponds to a flow of value $M$ with the same cost.

All capacities are integral, so an integral optimal flow exists. A bomb is selected exactly when its capacity-$1$ edge carries one unit of flow. Both transformations preserve the total cost, so the minimum flow cost is the answer.

The graph has $N+1$ vertices and $O(N+M)$ edges. A successive shortest augmenting path algorithm with Dijkstra and potentials performs at most $M$ augmentations, giving time complexity $O(M(N+M)\log N)$ and space complexity $O(N+M)$.

Solution written by GPT5.6