TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

100.0% (2/2)

Tags

Description

遠古時代,烏龜還不會飛,曾有座由 $N$ 個烏龜想要相互堆疊成一座塔。每一隻烏龜可以用兩個屬性來形容:第 $i$ 隻烏龜有一個「重量」 $w_i$ 與一個「過動度」$f_i$。現在,這些烏龜們想要依某種順序堆疊成一個塔,要最少化「麻煩度」。麻煩度的計算方法如下:

對於每一隻烏龜,其「過動度」$f_i$ 代表了它會想要出去幾次。而每次要出去,在其上方的烏龜都必須移開。具體來說,第 $i$ 隻烏龜會想要出去 $f_i$ 次,且每次都要花費 $w_1 + w_2 + w_3 + \dots + w_{i - 1}$ 的麻煩度,總麻煩度 $f_i(w_1 + w_2 + w_3 + \dots + w_{i - 1})$。舉例來說,如果有三隻烏龜烏龜從上到下的重量依序為 $[1, 2, 3]$,過動度為 $[4,5,6]$,則其麻煩度可以計算為 $1 \times 0 + 2 \times 4 + 3 \times (4 + 5) = 35$。

給你這 $N$ 隻烏龜的相關資料,請計算出它們堆疊成塔之後所可以達成的最小「麻煩度」。以上面的例子來說,那三個烏龜的最佳解是從上到下 $w = [3,2,1]$、$f = [6,5,4]$,的話,那麻煩度就是 $3 \times 0 + 2 \times 6 + 1 \times (6 + 5) = 23$(第一個範例測資)。

Input Format

輸入將有三行。第一行會是 $N$($1 \le N \le 10^ 5$),代表烏龜的數量。接下來第二行會有 $N$ 個正整數 $w_1, w_2, w_3, w_4 ,\dots, w_N$,而第三行也會有 $N$ 個正整數 $f_1, f_2, f_3, f_4 ,\dots, f_N$($1 \leq w_i, f_i \leq 1000$)。

此外:

  • 對於佔分 $10\%$ 的測試資料,額外滿足 $N = 2$,且取用次數 $f_1=f_2=1$。
  • 對於佔分 $20\%$ 的測試資料,額外滿足 $N = 3$。
  • 對於佔分 $45\%$ 的測試資料,額外滿足 $N \le 1000$,且對於所有 $1 \leq i \leq N$,$f_i = 1$。

Output Format

請輸出一個數字代表答案。

Sample Input 1

3
1 2 3
4 5 6

Sample Output 1

23

Sample Input 2

7
7 7 7 7 7 14 49
7 1 2 2 7 1 2

Sample Output 2

280

Hints

Problem Source

APCS 2017.10.18

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 2~6 $N = 2$,且取用次數 $f_1=f_2=1$。 10
3 7~13 $N = 3$ 20
4 2~6, 14~20 $N \le 1000$,且每一個物品 $i$ 的取用次數 $f_i=1$ 45
5 0~29 無額外限制 25

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1 5
1 1000 65536 65536 1 5
2 1000 65536 65536 2 4 5
3 1000 65536 65536 2 4 5
4 1000 65536 65536 2 4 5
5 1000 65536 65536 2 4 5
6 1000 65536 65536 2 4 5
7 1000 65536 65536 3 5
8 1000 65536 65536 3 5
9 1000 65536 65536 3 5
10 1000 65536 65536 3 5
11 1000 65536 65536 3 5
12 1000 65536 65536 3 5
13 1000 65536 65536 3 5
14 1000 65536 65536 4 5
15 1000 65536 65536 4 5
16 1000 65536 65536 4 5
17 1000 65536 65536 4 5
18 1000 65536 65536 4 5
19 1000 65536 65536 4 5
20 1000 65536 65536 4 5
21 1000 65536 65536 5
22 1000 65536 65536 5
23 1000 65536 65536 5
24 1000 65536 65536 5
25 1000 65536 65536 5
26 1000 65536 65536 5
27 1000 65536 65536 5
28 1000 65536 65536 5
29 1000 65536 65536 5