{"id":"2db4a9d3-dde8-442d-8c43-b091c311f667","name":"Highway Billboard","description":"1. You are given a number M representing length of highway(range).\r\n2. You are given a number N representing number of bill boards.\r\n3. You are given N space separated numbers representing (P)position of bill-boards.\r\n4. You are given N space separated numbers representing (R)revenue corresponding to each (P)position.\r\n5. You are given a number T such that bill-boards can only be placed after specific distance(T).\r\n6. Find the maximum revenue that can be generated.","inputFormat":"A number M(length of highway)\r\nA number N(number of bill boards)\r\nP1 ,P2 ,P3 ,P4 ,P5 .... Pn (placement of N bill-boards)\r\nR1 ,R2 ,R3 ,R4 ,R5 .... Rn (revenue from each bill-board)\r\nA number T (neccessary distance b/w two bill-board)","outputFormat":"Find the maximum revenue that can be generated.\r\nCheck the sample output and question video.\r\n","constraints":"1 &lt;= M &lt;= 100000\r\n1 &lt;= N &lt;= 50000\r\n1 &lt;= Pi &lt;= M\r\n1 &lt;= Ri &lt;= 100\r\n1 &lt;= T","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.util.Scanner;\r\npublic class Main{\r\n public static int solution(int m , int[] x, int[] rev, int t) {\r\n // write your code here\r\n return -1;\r\n }\r\n public static void input(int []arr,Scanner scn){\r\n for(int i = 0;i<arr.length;i++){\r\n arr[i] = scn.nextInt();\r\n }\r\n }\r\n public static void main(String []args){\r\n Scanner scn = new Scanner(System.in); \r\n int m = scn.nextInt();\r\n int n = scn.nextInt();\r\n \r\n int x[] = new int[n];\r\n input(x, scn);\r\n\r\n int revenue[] = new int[n];\r\n input(revenue,scn);\r\n\r\n int t = scn.nextInt();\r\n\r\n System.out.println(solution(m, x, revenue, t));\r\n scn.close();\r\n }\r\n}"},"node":{"code":""},"ruby":{"code":""},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"20\r\n5\r\n6 7 12 14 15\r\n5 8 5 3 1\r\n5","sampleOutput":"11\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"5539a6e8-c8bf-4f04-805c-e43e9d20e72a","name":"Dynamic Programming For Intermediate","slug":"dynamic-programming-for-intermediate-408","type":0},{"id":"65436969-8531-4a30-b5ff-dbf2ab2c8960","name":"Highway Billboard","slug":"highway-billboard","type":1}],"next":{"id":"3083a439-4154-4843-aa37-6a4550f9394d","name":"Temple Offerings","type":1,"slug":"temple-offerings"},"prev":{"id":"686ba90f-0d2a-461e-9ea1-2b5b4321a1cb","name":"Largest Square Sub-matrix With All 1's","type":1,"slug":"largest-square-sub-matrix-with-all-1-s"}}}

Highway Billboard

1. You are given a number M representing length of highway(range). 2. You are given a number N representing number of bill boards. 3. You are given N space separated numbers representing (P)position of bill-boards. 4. You are given N space separated numbers representing (R)revenue corresponding to each (P)position. 5. You are given a number T such that bill-boards can only be placed after specific distance(T). 6. Find the maximum revenue that can be generated.

{"id":"2db4a9d3-dde8-442d-8c43-b091c311f667","name":"Highway Billboard","description":"1. You are given a number M representing length of highway(range).\r\n2. You are given a number N representing number of bill boards.\r\n3. You are given N space separated numbers representing (P)position of bill-boards.\r\n4. You are given N space separated numbers representing (R)revenue corresponding to each (P)position.\r\n5. You are given a number T such that bill-boards can only be placed after specific distance(T).\r\n6. Find the maximum revenue that can be generated.","inputFormat":"A number M(length of highway)\r\nA number N(number of bill boards)\r\nP1 ,P2 ,P3 ,P4 ,P5 .... Pn (placement of N bill-boards)\r\nR1 ,R2 ,R3 ,R4 ,R5 .... Rn (revenue from each bill-board)\r\nA number T (neccessary distance b/w two bill-board)","outputFormat":"Find the maximum revenue that can be generated.\r\nCheck the sample output and question video.\r\n","constraints":"1 &lt;= M &lt;= 100000\r\n1 &lt;= N &lt;= 50000\r\n1 &lt;= Pi &lt;= M\r\n1 &lt;= Ri &lt;= 100\r\n1 &lt;= T","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.util.Scanner;\r\npublic class Main{\r\n public static int solution(int m , int[] x, int[] rev, int t) {\r\n // write your code here\r\n return -1;\r\n }\r\n public static void input(int []arr,Scanner scn){\r\n for(int i = 0;i<arr.length;i++){\r\n arr[i] = scn.nextInt();\r\n }\r\n }\r\n public static void main(String []args){\r\n Scanner scn = new Scanner(System.in); \r\n int m = scn.nextInt();\r\n int n = scn.nextInt();\r\n \r\n int x[] = new int[n];\r\n input(x, scn);\r\n\r\n int revenue[] = new int[n];\r\n input(revenue,scn);\r\n\r\n int t = scn.nextInt();\r\n\r\n System.out.println(solution(m, x, revenue, t));\r\n scn.close();\r\n }\r\n}"},"node":{"code":""},"ruby":{"code":""},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"20\r\n5\r\n6 7 12 14 15\r\n5 8 5 3 1\r\n5","sampleOutput":"11\r\n","questionVideo":"","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"5539a6e8-c8bf-4f04-805c-e43e9d20e72a","name":"Dynamic Programming For Intermediate","slug":"dynamic-programming-for-intermediate-408","type":0},{"id":"65436969-8531-4a30-b5ff-dbf2ab2c8960","name":"Highway Billboard","slug":"highway-billboard","type":1}],"next":{"id":"3083a439-4154-4843-aa37-6a4550f9394d","name":"Temple Offerings","type":1,"slug":"temple-offerings"},"prev":{"id":"686ba90f-0d2a-461e-9ea1-2b5b4321a1cb","name":"Largest Square Sub-matrix With All 1's","type":1,"slug":"largest-square-sub-matrix-with-all-1-s"}}}
plane

Editor

Loading...

Highway Billboard

medium

1. You are given a number M representing length of highway(range). 2. You are given a number N representing number of bill boards. 3. You are given N space separated numbers representing (P)position of bill-boards. 4. You are given N space separated numbers representing (R)revenue corresponding to each (P)position. 5. You are given a number T such that bill-boards can only be placed after specific distance(T). 6. Find the maximum revenue that can be generated.

Constraints

1 <= M <= 100000 1 <= N <= 50000 1 <= Pi <= M 1 <= Ri <= 100 1 <= T

Format

Input

A number M(length of highway) A number N(number of bill boards) P1 ,P2 ,P3 ,P4 ,P5 .... Pn (placement of N bill-boards) R1 ,R2 ,R3 ,R4 ,R5 .... Rn (revenue from each bill-board) A number T (neccessary distance b/w two bill-board)

Output

Find the maximum revenue that can be generated. Check the sample output and question video.

Example

Sample Input

20 5 6 7 12 14 15 5 8 5 3 1 5

Sample Output

11

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode