Given a set of vertical pillars of integer heights and unit width, we consider arranging them in a line. Rainwater can be trapped between the pillars. The goal is to determine all possible total volumes of trapped rainwater (in unit volumes) achievable across all possible arrangements of the pillars.

For example, with pillars of heights (1,5,2,1,4), one arrangement can trap 5 units of water.

Solution Approach

A key observation is that for a given pillar of height (h_x), any water volume that could theoretically be held above it (up to certain limits) is achievable through some arrangement. This can be proven by considering an insertion process from tallest to shortest pillars.

We can model the problem using dynamic programming optimized with a bitset. Let (a_1, a_2, \dots, a_n) be the sorted pillar heights in non-decreasing order. We maintain a bitset ans where ans[v] = 1 indicates that water volume (v) is achievable. We initialize ans[0] = 1 (zero water is always possible).

For each pillar (i) (except the tallest), we consider differences in height with taller pillars (j > i). The difference (a_j - a_i) represents a potential incremental water volume that can be added by appropriately placing pillar (i) relative to pillar (j). We use an auxiliary bitset f to accumulate new achievable volumes for the current (i), then udpate the main bitset ans.

Algorithm Steps:

1. Sort the pillar heights.
2. Initialize bitsets ans and f.
3. For each index i from 1 to n-1:
   • Clear f.
   • For each index j from i+1 to n-1:
     • Set f |= ans << (a[j] - a[i]).
   • Update ans |= f.
4. Output all indices where ans is set.

Proof Sketch: The process simulates adding pillars in order of increasing height. The operation ans << (a[j] - a[i]) generates all volumes achievable by adding the incremental water capacity created between pillars i and j. The combinatorial argument ensures all configurations are reachable.

Implemantation:

#include <bits/stdc++.h>
using namespace std;

const int MAX_VOLUME = 505 * 50; // Upper bound on total volume

bitset<MAX_VOLUME> currentStates, newStates;
int pillarHeights[505];
int numPillars;

int readInt() {
    int value = 0;
    char ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) {
        value = (value << 1) + (value << 3) + (ch - '0');
        ch = getchar();
    }
    return value;
}

int main() {
    numPillars = readInt();
    for (int idx = 1; idx <= numPillars; ++idx) {
        pillarHeights[idx] = readInt();
    }
    sort(pillarHeights + 1, pillarHeights + numPillars + 1);
    
    currentStates[0] = 1; // Zero water is always achievable
    
    for (int i = 1; i < numPillars; ++i) {
        newStates.reset();
        for (int j = i + 1; j < numPillars; ++j) {
            int heightDiff = pillarHeights[j] - pillarHeights[i];
            newStates |= currentStates << heightDiff;
        }
        currentStates |= newStates;
    }
    
    for (int vol = 0; vol < MAX_VOLUME; ++vol) {
        if (currentStates[vol]) {
            printf("%d ", vol);
        }
    }
    return 0;
}

Complexity: The algorithm runs in (O(n^2 \cdot \frac{V}{w})) where (V) is the maximum total volume and (w) is the word size (for bitset operations).