Cách Ly

View as PDF

Submit solution

All submissions

Best submissions

Points: 100.00 (partial)

Time limit: 0.5s

Memory limit: 1G

Input: stdin

Output: stdout

Author:

LeVanThuc

Problem type

Allowed languages

C++, Pascal, Python

Sau một cuộc thí nghiệm, MH khám phá ra $n$ loài sinh vật mới. Sinh vật thứ $i$ có độ nguy hiểm $a_{i}$ và chi phí cách ly là $b_{i}$ , với mỗi $i < j$ thì $a_{i} \leq a_{j}$ và $b_{i} \geq b_{j}$ . Cô ấy cần cách ly $n$ sinh vật này, tuy nhiên, vì vấn đề kinh phí, MH sẽ phải cách ly những sinh vật này thành từng nhóm liên tiếp nhau từ trái sang phải. Chi phí để cách ly một nhóm sinh vật với $i$ là sinh vật đầu nhóm, $j$ là sinh vật cuối nhóm là $a_{i} * b_{j} + b_{i}^{2} * a_{j}^{2}$ . Vì trước giờ chỉ học mỗi sinh nên MH không biết phải chia nhóm như nào để tốn ít chi phí nhất, các bạn hãy giúp cô ấy nhé!</p>

INPUT

Dòng đầu tiên gồm $1$ số nguyên dương $n (n \leq 10^{6})$ .
Dòng thứ hai gồm $n$ số nguyên dương $a_{i} (a_{i} \leq 10^{6})$ .
Dòng thứ ba gồm $n$ số nguyên dương $b_{i} (b_{i} \leq 10^{3})$ .

OUTPUT

Một số nguyên dương duy nhất là chi phí tối thiểu.

Sample Input

Copy

7
2 5 5 8 13 15 19
20 17 15 7 4 4 4

Sample Output

Copy

Subtask

Subtask 1: $b_{i} = 1$ (7p)
Subtask 2: $n \leq 10^{3}$ (28p)
Subtask 3: $n \leq 10^{6}$ (35p)

Giải thích

1 cách chia nhóm để có chi phí là 17960, chia làm 4 nhóm :
Nhóm 1 bao gồm 1 với chi phí là 1640
Nhóm 2 bao gồm 2-> 3 với chi phí là 7300
Nhóm 3 bao gồm 4 với chi phí là 3192
Nhóm 4 bao gồm 5->7 với chi phí là 5828
1640+7300+3192+5828=17960

Comments

Please read the guidelines before commenting.

3

LeVanThuc commented 3:03:53 pm, 16/03/2023

https://ideone.com/rEGZg0