CPSCO2019 Session3 C - Delicious Burgers

https://atcoder.jp/contests/cpsco2019-s2/submissions/15106499

• 括弧の深さは累積和
• 正常な括弧列なら累積和が負にならない
• 正常な括弧列なら末尾で累積和が0になる

問題文が分かりづらいが、サンプルからエスパーすると括弧の深いところに | を挟むと美味しさが増加すると分かる。累積和で各括弧の深さを計算し、貪欲に降順K個の和を取ると答えになる。