agc018_c

https://gyazo.com/a699700f574f70d6d75e4d04dcf31e26

考えたこと

まず全部をAにして、それから「Bに変えた時の得」「Cに変えた時の得」をソートして、大きい方から取っていく

これだと多分ダメなのだ。「Bにしても損だけどCにするとものすごく損だからBにするしかない」のパターンがあるから

公式解説

2種類の時には差でソートして大きい方から取っていく貪欲アルゴリズムが成立するので、問題を変形してからに帰着したい

B-Aでソートした場合にAがBより左に来ることはない、その場合、交換しても悪化しないから

なので境界線を引けば2種類の問題に帰着できる