Wells in the desert
Statement
One road runs east to west across a desert, and N wells stand along that road. The wells are numbered from the western end, well 1, well 2 and so on in order, with well N at the eastern end. A merchant leading a camel has to travel from well 1 to well N.
The camel travels a distance of exactly 1 on one barrel of water. Crossing a stretch therefore takes as many barrels as the distance of that stretch. Water can only be bought at a well, and the price of one barrel is set at each well. Two wells can have the same price. The camel can carry any number of barrels, so plenty of water can be bought ahead of time at a cheap well and used later. The merchant has no water at the start.
Given the distances between the wells and the price of water at each well, write a program that finds the smallest amount spent on water to travel from well 1 to well N.
For example, suppose there are N=4 wells and the price of one barrel at each well is the one in the following table.
| Well | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| Price of one barrel | 5 | 2 | 4 | 1 |
Also suppose the distance between each two neighboring wells is the one in the following table. The stretches run from the west in order and there are N-1 of them.
| Stretch | Well 1 to well 2 | Well 2 to well 3 | Well 3 to well 4 |
|---|---|---|---|
| Distance | 2 | 3 | 1 |
The water for a stretch can only be bought at a well that stands west of that stretch. So the water for each stretch should be bought at the cheapest of the wells passed up to that stretch. Working that out stretch by stretch gives the following.
| Stretch | Well 1 to well 2 | Well 2 to well 3 | Well 3 to well 4 |
|---|---|---|---|
| Distance | 2 | 3 | 1 |
| Cheapest price among the wells passed | 5 | 2 | 2 |
| Amount spent on water | 10 | 6 | 2 |
Adding up the water costs of the three stretches gives 18, so the answer in this example is 18. The price at well 3 is 4 but the price at well 2 is 2, so the water for the stretch from well 3 to well 4 comes cheaper when it is bought ahead of time at well 2. The price at well 4 is 1, the cheapest of all, but the road ends on arrival there, so there is nowhere to use it.
The distances and the prices each run up to 1,000,000,000 and there are up to 99,999 stretches, so the answer can grow past 1,000,000,000,000,000,000. The sum has to be taken with something that handles large integers so that no number overflows.
Input and output examples
Example 1
Input
4 2 3 1 5 2 4 1
Output
18
Example 2
Input
2 454 381 461
Output
172974
Example 3
Input
5 149 237 865 457 123 295 3 429 312
Output
51444
Input
The first line gives the number of wells N. N is a natural number from 2 to 100,000.
The second line gives the distances between neighboring wells, N-1 of them from the west in order, separated by one space. Each distance is a natural number from 1 to 1,000,000,000.
The third line gives the price of one barrel of water at each well, N of them from well 1 to well N in order, separated by one space. Each price is a natural number from 1 to 1,000,000,000.
Output
Print the smallest amount spent on water to travel from well 1 to well N on the first line.
Print one number and then a newline. Do not add any other character or space before or after it.
Requirements
- Read the input from standard input and write the answer to standard output
- There are N-1 distances and N prices. Take care that the two lines hold different counts of numbers
- The water for a stretch has to be bought at a well that stands west of that stretch
- There is no limit on how many barrels can be carried. Plenty may be bought ahead of time at a cheap well
- The answer can go past 2 to the power of 53, so adding with double-precision floating point throws the value off. Use something that handles large integers
- The output is one number and a newline, nothing else
- Grading compares the output with the expected value down to the last character
- You must write a program that reads from standard input and writes to standard output
- Trailing spaces at the end of a line and blank lines at the end of the output are ignored when grading
- The languages you can use are Python and JavaScript
- The memory limit is 256MB. The browser does not measure it, it only states it
- The time limit is set by measuring the setter's reference solution on the same runtime
- On this problem you submit code, not a prompt. That code runs in the browser on this device, and all that goes to the server is a fingerprint of the output and the time it took. Whether it is correct is decided by the server. The run time is a number each device reports, so the code and the device details are posted next to it on the leaderboard.
- There are 15 cases, and 3 of them show the input together with the expected output. The rest are used only when you submit and are not shown on this page.
- You have to pass all 15 cases to solve this.
Examples
3 public cases. Judging also uses hidden cases. You have to pass all 15 cases to solve this.
2 454 381 461
172974
5 149 237 865 457 123 295 3 429 312
51444
4 2 3 1 5 2 4 1
18
Solution
Your code runs on this device. Only the fingerprint of the output and the elapsed time go to the server. The server decides whether it is correct.
Submitting requires you to log in. Running against the public cases works without one.
You can test with 3 public cases. Submitting runs the hidden cases too.
People who solved this problem
The time shown is the time spent solving. Input reading time is outside the solver's control, so it is excluded. And since each device reports this value itself, we record which device measured it.
Log in and you can see the code once you solve this problem.