Recently De-shaw visited our campus for intern hiring and I am unable to solve this problem.
- Destruction Game
Thanos is on his mission to destroy the universe.
He comes across a new galaxy “Ravura”. There
are n planets lined up one after the other in
Ravura.
Thanos wants to destroy this galaxy, for which he
will have to destroy each planet.
Thanos can destroy a planet Pi ( 1 <=i<=n ) by:
• Firing a bomb at Pi, but it incurs him a cost
ci.
•If Pi-1 & Pi+1 have been destroyed , Thanos
can destroy Pi (1 < i < n )with a snap of his
fingers. This does not incur him any cost .
You are given a function destroy with 2
parameters. Return the minimum cost Thanos
should incur to destroy all the planets in Ravura.
Parameter:
- A binary array p, where ‘O’ and ‘1’ represent
existent and destroyed planets respectively.
(Seems Ronan has already done some part of
the work. ) - An integer array c , where ci represents the
cost of destroying a planet.
Input Format:
The locked code stub in the editor reads the
following input from stdin:
First line contains the value n, the size of array p.
Next n lines contains the elements of the array p.
Next line contains the value n, the size of array c.
Next n lines contains the elements of the array c.
Constraints:
1<=n<=10^5
0<=p[i]<=1 where (1<=i<= n)
1<=c[i]<=10^9 where(1<=i<= n)
Output Format:
Return an integer from the function destroy.
Sample Input 1:
4
0
1
1
0
4
1
1
1
1
Sample Output 1:
2
function to complete is
long destroy(vector p, vector c){
}