P2793 Facer's Factory

Facer is a part-time worker in a factory, and this time he encounters a problem. There are $N$ steel pipes, with the $i$-th pipe having length $a_i$. There is a pipe processor that can process $K$ units of pipe length per second. Facer needs to process these pipes in order. The machine has a maximum waiting length $H$, meaning the total length of pipes waiting to be processed (already fed into the machine but not yet processed) cannot exceed $H$ (guaranteed that $a_i \le H$). Facer can only feed pipes into the machine at integer seconds. What is the minimum time for Facer to finish processing all the pipes?

The first line contains $N, H, K$, representing the number of pipes, the maximum waiting length, and the processing speed per second. The next $N$ lines each contain one number, the length of a pipe. The pipes must be processed in order.

The minimum time.

Sample 1 explanation: There is only $1$ pipe, and the processing time is $\lceil 5/3 \rceil = 2$. Sample 2 explanation: - At the first second, feed $5$, waiting length is $5$. The machine processes $3$, waiting length becomes $2$. - At the second second, feed $4$, waiting length is $6$. The machine processes $3$, waiting length becomes $3$. - At the third second, feed $3$, waiting length is $6$. The machine processes $3$, waiting length becomes $3$. - At the fourth second, feed $1, 2$, waiting length is $6$. The machine processes $3$, waiting length becomes $3$. - At the fifth second, feed nothing, waiting length is $3$. The machine processes $3$, and all pipes are finished. Constraints: $N \le 100000$, $H, a_i \le 10^9$. Problem by zhouyonglong. Translated by ChatGPT 5