SPA - Spaceships in Space
Aliens attack! Run for your lives!
... or not, it's only a video game. And even then, although alien spaceships are flying straight for the Earth, it's not terribly important to destroy them all. Gregory the Gamer only wants that sweet high score.
To be more precise, there are n enemy spaceships, flying in a row. Every spaceship is of one of three colours. Our own spaceship is flying opposite of those, from left to right, and can destroy any of them. Destroying a spaceship of colour i is worth pi points. If you destroy more than one spaceship of the same color in a row, you get more points - second spaceship in sequence is worth 2pi points, for the third one you get 3pi and so on. The maximum number of points you can get for one spaceship is limited by M - if the previous rule dictates more than that, you get exactly M points instead.
What is the highest score Gregory can get?
The first line contains a single integer t, denoting number of testcases. Then, testcases follow.
The first line of a testcase contains two integers n, M - number of spaceships and points limit for one spaceship ( 1 <= n <= 105, 1 <= M <= 100 ).
In the next line there are three integers 1 <= pA, pB, pC <= M - point values for destroying spaceships of different colours.
In the last line there is a string of length n - description of subsequent spaceships. Every character is one of the following: A, B, C. Different characters correspond to different colours.
For every testcase you should output one integer - highest score you can get.
2 7 5 1 1 5 AAACAAA 6 10 1 1 10 ABABAB
In the first testcase we destroy all six spaceships of colour A, and we get 1+2+3+4+5+5 = 20 points. If we destroyed all of them instead, we'd get (1+2+3)+5+(1+2+3) = 17 points.
In the second testcase we can first destroy all spaceships of colour A, and then the last spaceship of colour B, which will give us (1+2+3)+1 = 7.
Great problem. Simple and clear description, but very interesting to implement and challenging to optimize. I will probably try to push my time down further.