Pepero Packing

Let $F_i=(B_i,U_i)$ be the optimal state using the first $i$ sticks: maximize boxes $B_i$, then minimize used sticks $U_i$. Leaving stick $i$ unused gives $F_{i-1}$. If the last box is the segment $k+1,\ldots,i$, it requires prefix sums $Q_i-Q_k\geq X$ and gives $(B_k+1,U_k+i-k)$. For a fixed last box the preceding prefix must be optimal, so this recurrence covers every solution. Subtask 1 checks every $k$ in $O(N^2)$ time. For the full task, positive weights make prefix sums increasing. The indices satisfying $Q_k\leq Q_i-X$ become eligible in order; a pointer adds each once. Keep the eligible state maximizing $B_k$ and, among ties, minimizing $U_k-k$. Compare its candidate with $F_{i-1}$ at every position. Time is $O(N)$ and space is $O(N)$.

Solution written by GPT6.1