TopCoder

User's AC Ratio

100.0% (10/10)

Submission's AC Ratio

84.6% (11/13)

Tags

Description

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

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

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

Input Format

輸入將有三行。第一行會是 N1N105),代表烏龜的數量。接下來第二行會有 N 個正整數 w1,w2,w3,w4,,wN,而第三行也會有 N 個正整數 f1,f2,f3,f4,,fN1wi,fi1000)。

此外:

  • 對於佔分 10% 的測試資料,額外滿足 N=2,且取用次數 f1=f2=1
  • 對於佔分 20% 的測試資料,額外滿足 N=3
  • 對於佔分 45% 的測試資料,額外滿足 N1000,且對於所有 1iNfi=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,且取用次數 f1=f2=1 10
3 7~13 N=3 20
4 2~6, 14~20 N1000,且每一個物品 i 的取用次數 fi=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