407872: GYM102911 H Heavy Sort

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

H. Heavy Sorttime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Cindy has started exercising regularly and doing physical conditioning. Inspired by her favorite anime series, she decided to clean up a beach full of trash that people had been treating as a dumping site for their junk. It simultaneously functions as strength training, and a way for her to do some good for society!

There are $$$N$$$ pieces of junk in a single line. From left to right, the $$$i$$$th piece of junk has a height of $$$H_i$$$ and a weight of $$$W_i$$$; it is guaranteed that the heights of each object are distinct. Cindy wishes to sort the junk in increasing order of height. The only operation that Cindy can do is to pick up two adjacent objects and swap their positions in the line. Since the objects can be heavy, the total energy that Cindy expends is the product of the weights of the two objects. Formally, Cindy can swap the positions of the $$$i$$$th and $$$(i+1)$$$th objects, and doing so costs $$$W_i \times W_{i+1}$$$ units of energy.

What is the minimum amount of energy that Cindy needs to expend in order to sort the junk in ascending order of height?

Input

The first line of input contains a single integer $$$N$$$, the number of pieces of junk.

The second line of input contains $$$N$$$ space-separated integers $$$H_1, H_2, \dots, H_N$$$, where $$$H_i$$$ is the height of the $$$i$$$th piece of junk.

The third line of input contains $$$N$$$ space-separated integers $$$W_1, W_2, \dots, W_N$$$, where $$$W_i$$$ is the weight of the $$$i$$$th piece of junk.

Output

Output a single integer, the minimum amount of energy that Cindy needs to expend to sort the junk in increasing order of height.

It is recommended that Python users submit to PyPy for this problem.

Scoring

$$$1 \leq N \leq 2\cdot 10^5$$$

$$$1 \leq H_i \leq 10^9$$$

$$$1 \leq W_i \leq 10^4$$$

It is guaranteed that $$$H_i \neq H_j$$$ for $$$i \neq j$$$.

Subtask 1 (35 points):

$$$N \leq 8$$$

Subtask 2 (15 points):

$$$N \leq 100$$$

Subtask 3 (20 points):

$$$N \leq 1000$$$

Subtask 4 (15 points):

All pieces of junk will have the same weight.

Subtask 5 (15 points):

No further constraints.

ExamplesInput
3
3 1 2
4 5 6
Output
44
Input
8
118 999 881 99 911 97 25 3
1 2 3 4 5 6 7 8
Output
501
Note

For the first sample test case, Cindy first swaps the objects of height $$$3$$$ and $$$1$$$, spending $$$4 \times 5 = 20$$$ energy. Then, she swaps the objects of height $$$3$$$ and $$$2$$$, spending $$$4 \times 6 = 24$$$ energy. The junk is now fully sorted in increasing order of height, and Cindy spent a total of $$$20+24 = 44$$$ energy.

加入题单

上一题 下一题 算法标签: