Overview

When books can be arranged in any order, we can simply calculate the total length when all required gaps are set to the minimum value \(K\), and this directly gives us the minimum distance.

Analysis

First, the distance we want to find is the length from “the left edge of the bookend” to “the right edge of the rightmost book.”

The arrangement (order of books) is free, but regardless of the order, the total thickness of the books \(\sum D_i\) remains the same. The “gaps” required by the rules are as follows:

• At least \(K\) between the bookend and the leftmost book
• At least \(K\) between each pair of adjacent books (if there are \(N\) books, there are \(N-1\) adjacent pairs)

Since we want to minimize the distance, it is optimal to make all these gaps exactly \(K\) (making them any wider only increases the distance).

Pay attention to the number of gaps:

• Bookend to 1st book: \(1\) gap
• Between books: \(N-1\) gaps

In total, \(1 + (N-1) = N\) gaps are needed, so the total length from gaps is \(N \cdot K\).

Therefore, the minimum distance is [ S + \sum_{i=1}^{N} D_i + N\cdot K ] and there is no need to optimize the order of books.

(Example) When \(N=3, S=10, K=2, D=[4,1,7]\): Total thickness \(=12\), there are \(3\) gaps so \(3\cdot2=6\). The answer is \(10+12+6=28\).

A naive approach of searching for the “optimal arrangement” (brute force) would require \(N!\) permutations and would never finish in time, but the above observation eliminates the need for any rearrangement.

Algorithm

1. Read \(N, S, K\) from input
2. Compute the total thickness \(T=\sum D_i\)
3. Output the answer as \(S + T + N\cdot K\)

Complexity

• Time complexity: \(O(N)\) (just summing up the thicknesses)
• Space complexity: \(O(1)\) (only a constant number of values like the sum. Constant if the implementation doesn’t store the input array)

Implementation Notes

• \(S, K, D_i\) can be up to \(10^9\) and \(N\) up to \(10^5\), so the answer can be approximately \(10^{14}\) at most. 64-bit integers are required, but Python’s int handles this safely.

• A typical pitfall is that the number of gaps is \(N\), not \(N-1\) (don’t forget the \(1\) gap between the bookend and the first book).

  Source Code

import sys

def main():
    it = iter(sys.stdin.read().strip().split())
    N = int(next(it))
    S = int(next(it))
    K = int(next(it))
    total_thickness = sum(int(next(it)) for _ in range(N))
    ans = S + total_thickness + N * K
    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.