Deepak loves to travel but he wants to minimize the total travel expenditure. His journey will be through N checkpoints. Checkpoints are numbered from 0 to N−1. At the start of his journey he is present at the checkpoint 0. Also checkpoint N−1 will lead to his final destination.
Each checkpoint has a petrol pump which can be used to fill petrol in the car. Now cost of petrol per litre at different checkpoints is given by array C which has 0-based indexing where C[i] is the cost per litre of petrol at the ith checkpoint. Note that there is an infinite amount of supply at each checkpoint and car tank is also of infinite capacity. Now another array L is given which has 0-based indexing where L[i] denotes the amount of petrol in litres required to reach the (i+1)th checkpoint from the ith checkpoint. Note that the extra petrol remaining in the tank does not vanishes after reaching a checkpoint. Also, Deepak should have atleast L[i] litres of petrol at each checkpoint in order to reach the next checkpoint.
Help Deepak to estimate the minimum cost required in order complete the journey.
Input Format:
First line of the input contains test cases denoted by T.
For each of the test cases, first line contains a single integers N denoting the number of checkpoints.
The next line contains N-space separated integers representing the array C which has 0-based indexing where the integer denotes the cost per litre of petrol at ith checkpoint.
The last line contains array L, which has 0-based indexing, consisting of N space separated integers where the ith integer denotes the required amount of petrol needed to reach the (i+1)th checkpoint from the ith checkpoint.
Constraints:
1≤T≤5 1≤N≤10^5 1≤C[i],L[i]≤10^5
Output Format
For each of the test cases, output the required answer in a separate line.
Sample Input
1
2
5 1
1 2
Sample Output
7
–> My code is giving correct answer for the sample test case.
i have even tried for some manual test cases and it is giving correct answer.
for example:
1
8
4 7 5 9 3 2 7 6
7 3 2 5 10 8 7 9
For this it is giving output 146.
1
6
5 2 4 1 2 2
2 1 2 3 4 4
And for this case it is giving output as 27 just as expected.
What is wrong with my code or logic? It is not even passing a single test case on submission.
My code–> https://ide.codingblocks.com/s/67973
Main logic: The position/checkpoint where the cost of petrol is least is noted down. At that checkpoint we purchase all the fuel needed to pass the further check points as this will contribute to minimum expenditure.This process is repeated.
example…for the above test case… 1 is the minm cost so fuel for all checkpoints after 1 is purchased at this rate. 2 is second lowest…so for all checkpoints after 2 and before 1, fuel is purchased at the rate of 2…and so on…