A cargo canal is divided into n consecutive segments, numbered 1 to n. Each segment can be traveled through one of two parallel lanes: the Standard lane or the Toll lane. Traveling segment i in the Standard lane costs standard_i; traveling it in the Toll lane costs toll_i. A convoy starts just before segment 1, in the Standard lane. At the start of any segment the convoy may move from the Standard lane into the Toll lane by paying a one-time gate fee fee (this fee may be paid again to re-enter the Toll lane later, if the convoy has since dropped back to Standard); moving back from the Toll lane into the Standard lane never costs anything. For every j from 1 to n, report the minimum total amount the convoy must have spent to finish traveling segments 1 through j, ending that prefix in whichever lane is cheaper.
Line 1: two integers n and fee.
Line 2: n integers standard_1 ... standard_n.
Line 3: n integers toll_1 ... toll_n.
n integers separated by single spaces, on one line: for each j from 1 to n, the minimum total cost to finish segments 1 through j.
Example 1
Input
3 2 1 2 1 3 1 1
Expected
1 3 4
Explanation
Segment 1: Standard costs 1, versus paying the fee and using Toll for 2+3=5 — Standard wins, running cost 1. Segment 2: continuing Standard costs 1+2=3; switching now would cost 1+2+1=4 — Standard still wins, running cost 3. Segment 3: continuing Standard costs 3+1=4; switching now costs 3+2+1=6 — the cheapest way to finish all 3 segments is 4. Output: 1 3 4.
Example 2
Input
5 4 1 1 1 1 1 2 2 2 2 2
Expected
1 2 3 4 5
Explanation
Standard costs 1 per segment while Toll costs 2 per segment even before the fee of 4 to enter it — Standard is always cheaper, so the convoy never switches, and the running totals after each segment are 1, 2, 3, 4, 5.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →