Official

A - Bridge and Sheets Editorial by evima


The uncovered part is divided into several segments. From the fact that the tarps have the same lengths, it can be shown that we can individually solve the problem for each segment.

Thus, the problem can be rephrased into the following.

There are \(n\) bridges without existing tarps. The length of the \(i\)-th bridge is \(l_i\). For each bridge, find the minimum number of tarps needed to cover it entirely. Then, find the sum of these numbers.

We need \(\lceil \frac{l}{W} \rceil\) tarps to cover a bridge of length \(l\). Therefore, the answer is \(\sum_{i=1}^{n}\lceil \frac{l_i}{W} \rceil\), which can be found in \(O(N)\) time.

posted:
last update: