便宜上，「床」を「重さ \(\infty\) の箱」と考えておくと，実装・考察が簡潔です．

\(i=1,2,\ldots\) 順に次を行う貪欲法が最適であることを示します．

• 重さ \(w_i\) の箱を置ける箱のうち，重さが最小の箱の上にこれを置く．

最適性は，「他の置き方の上位互換である」ことを確かめることによって証明できます．

例えば，現在の箱の状況が \((5, 10, 8, \infty)\) であるとき，重さ \(7\) の箱を置くことを考えましょう．置いた後の状態は

\((5,7,8,\infty)\), \((5,10,7,\infty)\), \((5,10,8,7)\)

のどれかです．このうち，\((5,7,8,\infty)\) と \((5,10,7,\infty)\) を比べてみます．箱を並べ替えればこれらを \((5,7,8,\infty)\) と \((5,7,10,\infty)\) と見なせます．すると，後者は単純にひとつの箱が重くなっており，単純な上位互換の関係になります．

\((5,10,8,7)\) も \((5,7,8,10)\) と並べ替えれば同様です．「床」を使ったことで箱の山の個数が増えていますが，これも条件は悪くなる一方です．

結局，次を繰りかえせばよいです：

• 重さ \(w_i\) の箱を置ける箱のうち，重さが最小の箱の上にこれを置く．

置ける箱を \(O(N)\) 時間かけて探索すれば，\(O(N^2)\) 時間で解くことができます．

\(O(N\log N)\) 時間で解くこともできます． 箱の重さが昇順になっているとき，箱を追加した後にも箱の重さが昇順である状態を保つことができます．すると，箱を置くべき場所が二分探索により取得できるようになります．

解答例：https://atcoder.jp/contests/arc006/submissions/42177216