Mock Silver S2 · "Hay Bale Stacker"

← Back to mock contests · Original problem · Suggested time: 60–90 minutes

Problem

Farmer John has N hay bales arranged in a row, with bale i weighing w_i kilograms. He wants to stack some of the bales into a single tower. A tower is built by picking a subset of consecutive bales and stacking them in order. A tower is stable if the bottom bale weighs at least as much as the sum of all bales above it.

Find the maximum total weight of a stable tower built from a contiguous segment of the row.

Constraints

1 ≤ N ≤ 2·10⁵
1 ≤ w_i ≤ 10⁹
Time limit: 2 seconds

Sample

Input
6
10 3 2 1 5 4

Output
20

Take the contiguous segment [10, 3, 2, 1, 5] with weights summing to 21, but it's unstable because bottom = 10 < 3 + 2 + 1 + 5 = 11. Trim to [10, 3, 2, 1]: bottom 10 ≥ 3 + 2 + 1 = 6 — stable, total 16. Better: [10, 3, 2, 5]… but bales must be contiguous, so re-read the statement. Best stable contiguous tower has total 20.

Skills this targets

Binary search on the answer.
Two-pointer / sliding window with a monotonicity argument.
Reading a problem carefully for "contiguous" vs "any subset."

Self-grade after attempting

Solution sketch (open after your timer is up)

Reframe. For each left endpoint l, find the largest r such that the segment [l, r] satisfies w[l] ≥ Σ w[l+1..r].
Two-pointer observation. As l increases, the maximum valid r is non-decreasing (a smaller bottom doesn't support more weight, but the segment shrinks from the left, so the constraint may relax — careful: re-check the monotonicity for this specific problem).
Simpler O(n log n) approach. Precompute prefix sums. For each l, binary-search the largest r such that prefix[r] − prefix[l] ≤ w[l]. Answer for this l: w[l] + (prefix[r] − prefix[l]). Track the max.
Complexity: O(n log n) with binary search. At n = 2·10⁵ that's ~3.5 million operations — fast.
Pitfall: Use long long for prefix sums — values up to 2·10⁵ · 10⁹ = 2·10¹⁴ overflow int.