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
hide comments
|
robosapien:
2020-12-25 22:01:07
check for (in case of WA)
|
|
Rafail Loizou:
2020-11-17 01:28:28
you can do this with memoization as well, it will work just make separate states for the beggining buff and the BAT buff so you don't get WAs. Also reset each time your arrays fully for all testcases. O(N^2) passes even with recursion. |
|
kumar_anubhav:
2020-08-17 12:42:28
means after reaching to mth index batman can explore all other hill ? if not then what exactly we have to do?? |
|
kushrike:
2020-05-09 23:20:34
he can only jump from m'th peak to any peak of his wish that lies from m+1 to n.
|
|
amansahu112:
2020-05-08 19:25:30
if he uses mini-bat then he can jump to any peak from m+1 till n |
|
abhinav_99:
2019-10-28 13:05:42
Same as longest increasing subsequence just reverse the condition and skip the comparison at the mth index. |
|
rishabh_jiit:
2019-07-06 10:47:16
Guys please skip this problem it has the worst problem statement .
|
|
god_coder:
2019-05-30 14:09:48
Very poor description of the problem. Extremely unclear statement |
|
spectre009:
2019-01-04 11:01:32
Very poor description, first of all bat can only be used at m and it is not important that Batman should start from 0 index. |
|
aman_sachin200:
2018-06-13 09:41:01
Nice one!!!Remember that BATMAN can use the BAT only on the peak where ROBIN is standing!!!!Cost me 1 WA :( |
| 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 |
RSS