#P4611. Jumping Skyscrapers

    ID: 17857 Type: Default 1000ms 256MiB

Jumping Skyscrapers

Jumping Skyscrapers

You are given a sequence of N skyscrapers, numbered from 1 to N from left to right. You start at skyscraper K. Each skyscraper has a height, and some skyscrapers are equipped with trampolines.

You can make a move from your current skyscraper i in one of the following ways:

  1. If you do not have a trampoline on skyscraper i, you can only jump to an adjacent skyscraper (either i-1 or i+1) if and only if the height of that adjacent skyscraper is less than or equal to the height of your current skyscraper. In other words, you can jump from skyscraper i to skyscraper j (where j = i-1 or i+1) if $$ h_j \le h_i. $$
  2. If you are on a skyscraper that has a trampoline, you can jump to any other skyscraper (regardless of its height or position).

Your task is to determine the maximum number of distinct skyscrapers you can reach (including the starting skyscraper), where even if a skyscraper is visited multiple times, it is only counted once.

inputFormat

The input consists of three lines:

  1. The first line contains two integers N and K (1 ≤ K ≤ N), representing the number of skyscrapers and the starting skyscraper index respectively.
  2. The second line contains N integers: h1, h2, ..., hN, where hi represents the height of the i-th skyscraper.
  3. The third line contains N integers (each either 0 or 1). The i-th integer indicates whether the i-th skyscraper is equipped with a trampoline (1 means it has a trampoline, 0 means it does not).

outputFormat

Output a single integer – the maximum number of distinct skyscrapers that can be reached starting from skyscraper K.

sample

5 3
10 5 2 6 8
0 0 0 0 0
1