theater

解説

方針

「快適に観る」ためには、同じ列において前の行にいる人がすべて自分より低い必要があります。
つまり、同じ列に同じ身長の人が 2 人以上並ぶと、後ろの人は快適ではなくなることに注意します。

よって、身長 $h$ について「快適になれる人数」は各列に高々 1 人、合計で $min(人数(h), W)$ 人です。
したがって、快適になれる人数の最大値は

$\sum_h \min(人数(h), W)$

となります。

配置方法

この上限を実現する方法を考えます。
観客を身長の昇順に並べ、前の行から順に左から右へ座席を埋めます。
すると、同じ列では必ず「下に行くほど身長が大きいか同じ」になります。
したがって、各列について

• 最前席の人は必ず快適
• それ以外は「直上の人より身長が大きいとき」だけ快適
  となり、最終的に上の式で示した上限ちょうどの人数が快適になります。

実装

1. 観客を (番号, 身長) の組で持ち、身長昇順にソートする。
2. 座席表を $-1$ で初期化し、前から順に埋める。
3. 快適かどうかは「最前席なら快適」「それ以外は一つ前の座席の人より身長が大きければ快適」で判定して数える。

計算量

• ソートに $O(N log N)$
• 座席への割り当てと判定に $O(N)$
  合計で $O(N log N)$ です。
  制約下で十分高速に動作します。

これで最大人数と一例の配置を構成できます。

実装例は以下のようになります。