「甘さの増分と辛さの増分の最大値を取る」かわりに、「甘さの増分と辛さの増分の好きな方を取る」としても答えは変化しません。

甘さと辛さのどちらを選ぶかがその前後で変化しない食べ物については、答えへの寄与は \(0\) です。一方、変化する食べ物にだけ注目すると、スコアに対して、 \(A_i\) と \(B_i\) のちょうど一方が+, もう一方が - に寄与することが分かります。すなわち、\(D_i = A_i - B_i\) として、答えへの寄与は \(+D_i\) あるいは \(-D_i\) です。そして、\(+D_i\) として寄与するものと \(-D_i\) として寄与するものが交互に現れることが分かります。

各食べ物が \(+D_i, -D_i, 0\) のうちどれで寄与するかに関する必要十分条件は、\(+D_i\) として寄与するものの個数と、 \(-D_i\) として寄与するものの個数の差の絶対値が \(1\) 以下であることです。

\(D_i\) を昇順に並べたとき、\(+D_i\) として寄与するものは後ろからいくつか、 \(-D_i\) として寄与するものは前からいくつか取れば良いです。計算量は \(O(N\log N)\) です。

また、 \(0\) として寄与するものは高々一つであることが示せるため、寄与の方法として考えられるものをさらに絞ることもできます。