COI '11 #4 Trampolin

View as PDF

Submit solution


Points: 17
Time limit: 0.5s
Memory limit: 64M

Problem types

There are many action superheroes out there: Batman, Spiderman, Superman, Icantwriteman etc. Among them, there is one gentleman called Kickass. Today he wants to mimic Spiderman, so he has chosen a row of tall skyscrapers to jump around on.

Specifically, he has chosen a sequence of N skyscrapers numbered 1 through N from left to right. He is initially located on the K^\text{th} skyscraper. Unfortunately, Kickass has very limited powers, and can therefore jump only to the adjacent skyscraper to the left or right, and only if that skyscraper's height is not greater than the height of the skyscraper he is currently on. However, anticipating this and not wanting to look weak, he has positioned trampolines on top of some skyscrapers, and from these skyscrapers he can jump onto any other skyscraper, no matter how tall or where that skyscraper is.

Find the maximum number of different skyscrapers Kickass can visit in a chain of jumps starting from the skyscraper numbered K. If a skyscraper is visited more than once, we still count it only once. Moreover, skyscraper K is counted even if we never return to it.

Input Specification

The first line of input contains the two integers N and K (3 \le N \le 300\,000, 1 \le K \le N), the total number of skyscrapers and the starting skyscraper, respectively.

The second line of input contains N integers less than 10^6, the heights of skyscrapers in order from left to right.

The third line of input contains a sequence of N characters . or T. If the i^\text{th} character is T, then there is a trampoline positioned on the top of skyscraper i.

Output Specification

The first and only line of output must contain the required maximum number of visited skyscrapers.

Sample Input 1

6 4
12 16 16 16 14 14
.T....

Sample Output 1

5

Sample Input 2

10 1
10 7 3 1 1 9 8 2 4 10
..T..T....

Sample Output 2

7

Explanation for Sample Output 2

The sequence of visited skyscrapers could be the following:

\displaystyle 1 \to 2 \to 3 \to 6 \to 10 \to 9 \to 8


Comments

There are no comments at the moment.