E: 3D プリント
問題
3次元空間に1辺長さsの立方体の設計図が n個ある。全ての立方体は3つの軸に平行で、頂点は整数座標。
ある2つの立方体が共通部分を持つとき連結しているといい、複数の立方体が次々に連結していれば大きな一つの立体になる。
n個の設計図からk個選んで立体を置いたとき、一つの立体に成るようにしなければならない。
このとき、その大きい立体の表面積の最小値を出力せよ。
入力のn個の立方体は次の条件を満たしている。
- 各立方体は0個・1個・2個の立方体と連結することはあるが、3個以上の立方体と連結することはない
- ある立方体が2個の立方体と連結するとき、その2つは連結していない
- どの2つの立方体も頂点・辺・面で接することはない。真に離れているか、真に共通部分を持つかのどちらかである