fares[i] is the ticket price for stop number i + 1. You need access to every stop on the route.
There is a promotion: buying the ticket for stop number i gives you the next i stops for free (numbers i + 1 through 2i). A stop you already got for free may still be bought, to get its own bonus.
Return the smallest total you need to pay to get every stop.fares=[4, 10, 1, 7] → 5
Buy stop 1 for 4, which makes stop 2 free. Buy stop 3 for 1, which covers stop 4 as well. Total: 5.
fares=[3, 1, 9, 9, 9] → 12
Buy stop 1 for 3, so stop 2 is free. Then buy stop 3 for 9, which covers stops 4, 5 and 6. Total: 12. The cheap stop 2 is tempting, but it does not cover stop 5, so 9 would have to be paid anyway.
fares=[6] → 6
fares=[4, 10, 1, 7]
5
Run checks the first 3 tests in your browser. Submit checks all 120 tests on the server, hidden ones included.