JOI 17 本選-美術展

考察

展示する最大の美術品と最小の美術品がどちらも不定だと考えづらいので、片方を固定してみます。ここでは最大を固定するとします。
まず、同じ大きさの美術品がない場合を考えます。
あらかじめ、美術品を大きさに関して昇順にソートしておきます。また、このもとでの価値についての累積和を保存する配列を ACM とします。
美術品 i が大きさ最大になる展示方法の評価値は、

S - (A_i - A_{min})

です。仮に最小の大きさを与える美術品が j (j < i) であるとすると、これは、

(ACM_i - ACM_j + B_j) - (A_i - A_j)
= (ACM_i - A_i) - (ACM_j  - B_j - A_j)

と書けます(最大値と最小値の間の大きさの美術品は全て展示したほうがいいので)。
つまり、

C_j = ACM_j - B_j - A_j

とおけば、評価値は ACM_i - A_i から C_j を引いたものになるわけです。C_j は「美術品 j の最小としての不適当さ」みたいなものです。
よって j < i の中での C_j の最小値が分かれば、最大を固定した上での最適値が分かります。
全ての美術品にわたる上記の最適値の max が答えであり、これは美術品を小さい方から走査していくことで O(N) で計算ができます。
最大値や最小値と同じ大きさの美術品は全て展示した方がいいことをふまえると、このアルゴリズムは重さが distinct でなくても正しく動きます。

コード

上書きして消えた