Stacking (APCS 2017-10 Expert)

An automated system has a subsystem for accessing items. The subsystem stacks N items on a vertical shelf, with each item occupying one level. The system works as follows: each time, only one item is accessed. To access it, the system must first raise the shelf levels above that item. After the item is accessed, it must be put back, and then the raised shelf levels are lowered back to their original positions before the next item is accessed.

The energy needed to raise some items is calculated by the total weight of those items. Here we ignore the weight of the shelf and all other possible costs. There are N items. The weight of item i is w(i), and it must be accessed f(i) times. Determine how to arrange these items so that the consumed energy is as small as possible.

For example, suppose there are two items with w(1)=1, w(2)=2, f(1)=3, and f(2)=4. That is, item 1 has weight 1 and must be accessed 3 times, while item 2 has weight 2 and must be accessed 4 times. There are two possible orders from top to bottom:

• (1,2): item 1 is above item 2. Accessing item 1 needs no energy, and each access to item 2 costs w(1)=1. Since item 2 must be accessed f(2)=4 times, the energy cost is w(1)*f(2)=4.
• (2,1): item 2 is above item 1. Accessing item 2 needs no energy, and each access to item 1 costs w(2)=2. Since item 1 must be accessed f(1)=3 times, the energy cost is w(2)*f(1)=6.

Among the two possible orders, the minimum energy is 4, so the answer is 4. As another example, suppose there are three items with w(1)=3, w(2)=4, w(3)=5, f(1)=1, f(2)=2, and f(3)=3. If the top-to-bottom order is (3,2,1), the energy is computed as follows: accessing item 3 needs no energy; accessing item 2 costs w(3)*f(2)=10; accessing item 1 costs (w(3)+w(2))*f(1)=9; the total energy is 19. If the order is (1,2,3), the energy cost is 3*2+(3+4)*3=27. In fact, there are 3!=6 possible orders in total, and the order (3,2,1) achieves the minimum energy 19.

Input Format

The first line contains the number of items N. The second line contains N positive integers, the item weights w(1), w(2), ..., w(N) in order. Each weight is at most 1000, and the integers are separated by single spaces. The third line contains N positive integers, the access counts f(1), f(2), ..., f(N) in order. Each access count is a positive integer at most 1000, and the integers are separated by single spaces.

Output Format

Output the minimum energy consumption value, followed by a newline. The answer will not exceed the positive integer range representable by 63 bits.

Sample Input 1

2
20 10
1 1

Sample Output 1

10

Sample Input 2

3
3 4 5
1 2 3

Sample Output 2

19

Scoring

The input contains several test cases. The time limit for each test case is 1 second. Points are awarded according to the number of correctly passed test cases:

Subtask 1 is worth 10 points: N = 2 and f(1)=f(2)=1.

Subtask 2 is worth 20 points: N = 3.

Subtask 3 is worth 45 points: N <= 1000, and every item i has f(i)=1.

Subtask 4 is worth 25 points: N <= 100000.

Source

APCS implementation contest, October 28, 2017, problem 4. Official PDF: https://apcs.csie.ntnu.edu.tw/wp-content/uploads/2018/12/1061028APCSImplementation.pdf