Codeforces C. Brutality 1107C Educational Codeforces Round 59 (Rated for Div. 2)

Problem link

All you need in this problem is two simple technique: two pointers and sorting. Let's consider maximum by inclusion segments of equal letters in the initial string. Let the current segment be [l;r] and its length is len=r−l+1. If len<k then we can press all buttons and deal all damage corresponding to them. Otherwise, it is obviously more profitable to press k best (by damage) buttons. So let's create the array value, push all values ai such that l≤i≤r in this array, sort them, take min(|val|,k) best by damage (|val| is the size of the array value) and go to the next segment.


A solution in c++