旨いステーキ(Delicious Steak)

すべてのステーキに酢をかける場合を基準にすると、基本点は $B=\sum_{i=1}^{3N}V_i$ である。$i$ 番目のステーキを A1 ソースに変えたときの増分は $A_i-V_i$、塩に変えたときの増分は $S_i-V_i$ となる。

ステーキを $A_i-S_i$ の降順に並べる。前にあるステーキが塩、後ろにあるステーキが A1 ソースなら、二つのソースを交換しても合計は減らない。よって、A1 ソースをかけるステーキがすべて塩をかけるステーキより前にある最適解が存在する。

その境界を $k$ とすると、$N\le k\le 2N$ である。先頭 $k$ 個から $A_i-V_i$ の大きい 個を選ぶ増分を 、残りの 個から の大きい 個を選ぶ増分を とすると、答えは

$$B+\max_{N\le k\le 2N}(P_k+Q_k)$$

となる。

最小ヒープを用いれば、各接頭部分の $P_k$ と各接尾部分の $Q_k$ を求められる。計算量は $O(N\log N)$、空間計算量は である。答えの絶対値は 以下なので、64 ビット整数を使う。

Solution written by GPT6