BAT3 - BATMAN3

Bruce Wayne: I do fear death. I fear dying in here while my city burns.
Blind Prisoner: Then make the climb.
Bruce Wayne: How?
Blind Prisoner: As the child did. Without the rope. Then fear will find you again.

The Epic fight between BANE and BATMAN saw BATMAN on the losing side. Bane delivers a crippling blow to Batman's back, then takes him to a foreign, well-like prison where escape is virtually impossible.

The prison as we know is a place from where no man ever escaped, except for the child of Ra's al Ghul himself.

The heroics of BATMAN saw him escape the prison, however after the prison came the Valleys. To reach the city, He needed to cross these valleys. Meanwhile, BANE's army has surrounded the city and trapped all the policemen underground. Each of these peaks contain exactly one policeman held captive by Bane's men. Since, BATMAN needs to build his own army, he decides to free some of the policemen on his way.

Also BATMAN needed to save his energy before his battle with Bane, so he decided to take only downhill (strictly) jumps. Detective John Blake (now called as ROBIN) is standing in one of these peaks with a mini-BAT. This will allow BATMAN to take a maximum one jump uphill ahead. BATMAN can choose to flee ROBIN and use the BAT or rather cross over without his help.

The task in hand is to maximize the army strength to face BANE as BATMAN crosses over. (BATMAN can take his first jump on any of these peaks)

Bane: So, you came back to die with your city.
Batman: No. I came back to stop you.

Input

t: number of testcases.

n: number of peaks.

m: (zero based) index of the peak where ROBIN is standing.

n integers denoting the height of the peaks.

Output

The maximum strength of the army.

Constraints

1<=n<=1000

Example

Input:
1
6 4
6 3 5 2 4 5

Output:
4

Added by:Romal Thoppilan
Date:2013-02-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem

hide comments
2016-09-12 14:06:56
@dush1729 @Dushyant Singh
you are entering n=9 and {8 4 5 3 10 5 6 7 2000 1999} these are 10 elements.
enter input as
1
10 5
8 4 5 3 10 5 6 7 2000 1999
and you will get answer as 4.
2016-08-28 00:53:19
:) yaa...
LIS with a relaxation in a particular case.
2016-07-05 14:27:09
LIS problem with one more condition!!
@Dushyant answer will be 3 only!!
the thing is that he cannot carry the bat mobile! hope dis helps.
2016-03-06 15:12:45 Dushyant Singh
Correct me if I am wrong.
Shouldn't the answer for this test case be 4

1
9 5
8 4 5 3 10 5 6 7 2000 1999

I got AC using code which gave answer 3.
2016-02-19 21:06:08
He can't carry the bat mobile!!! :'(
got many WAs due to this!!!
2016-02-03 19:30:32 sai krishna
Standard LIS with Little Variation
2015-08-19 07:17:03 The_ROCK
Some clarifications:
1. Batman cannot jump backwards (with or without the BAT).
2. Batman can jump to any peak ahead from Robin's position(and not just to the immediate next peak) with the help of BAT
2015-07-03 00:04:02 thewatch
while using the mini-BAT can the batman jump over multiple peaks ie pass one peak
for example
6 1
6 10 8 13 12 11
so can he use the mini-BAT at 10 and jump to 13
answer is 10->13->12->11 OR 10 ->8
2014-05-22 09:23:24 dunnohyet
how can batman cross the last peak without jumping on it??
Also can he skip peaks while jumping..as in
3 0
5 3 4
can he jump from 0 to 2??

Last edit: 2014-05-22 09:27:55
2014-03-13 19:20:47 Guilherme Sena
If he can't carry the bat and has to use it in the peak in which robin is, how can the solution 4 in the test case be possible? The only possible (maximum) paths are: 6-3, 3, 5-3, 5-2, 2, 4-2, 4, and 5-4-2, none of which results in 4. Does batman count in the army as well?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.