All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem

Maximum Profit
/
No tags
Problem
Editorial
Analytics

Sati has been invited to a give away contest. She is left standing in front of two simultaneously moving conveyor belts with N items of different worths placed on each of them and all she has to do is collect items resulting to maximum sum. The conveyor belts are given in the form of two arrays of size N each and due to the moving belts, for an index i she can only pick one item from the two and after that she cannot pick from any index j < i. But, remember she can pick any number of items from the same belt but as she picks an item from other there is a penalty of worth X. Help her maximise her profit.......For better understanding do have a look on the sample test case.

INPUT FORMAT

  • First line: Two space seperated integers N and X denoting the size of two arrays and the penalty for switching belts respectively.
  • Second line: space seperated integers representing worth of items on first belt;
  • Third line: space seperated integers representing worth of items on second belt;

OUTPUT FORMAT

Print a single integer representing the maximum achievable sum. 

 

CONSTRAINTS

0 < N <=10^5 ,  0<= X <=10^9

0 < A[i] <=10^9  , 0 < B[i] <=10^9

 

SUBTASKS

Subtask #1 (20 points): = 0;

Subtask #2 (80 points): Original constraints

SAMPLE INPUT
6 2
1 2 3 4 7 1
4 5 1 4 1 7
SAMPLE OUTPUT
26
Explanation

4 -> 5 -> (3-2) -> 4 -> 7 -> (7-2)

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

Initializing Code Editor...
Notifications
View All Notifications

?