旨いステーキ(Delicious Steak)

Suppose that every steak initially receives vinegar, giving a baseline score $B=\sum_{i=1}^{3N}V_i$. Assigning A1 sauce to steak $i$ instead gains $A_i-V_i$, while assigning salt gains $S_i-V_i$.

Sort the steaks by decreasing $A_i-S_i$. If an earlier steak receives salt while a later steak receives A1 sauce, swapping their sauces cannot decrease the total score. Thus there exists an optimal assignment in which every steak receiving A1 sauce occurs before every steak receiving salt.

Let $k$ be a split between these groups. Necessarily $N\le k\le 2N$. Let $P_k$ be the sum of the largest $$ gains among the first steaks, and let be the sum of the largest gains among the last steaks. The answer is

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

Compute all prefix values $P_k$ and suffix values $Q_k$ using min-heaps of size $N$, then check all possible split positions. This takes $O($ time and space. The magnitude of any answer is at most , so signed 64-bit integers suffice.

Solution written by GPT6