Khai Thác Gỗ

Điểm: 7,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Có $n$ cái cây với chiều cao $a_{1}, a_{2}, \dots, a_{n}$ . Bạn cần chặt tất cả các cây xuống chiều cao $0$ bằng một cái cưa máy.

Mỗi lần dùng cưa máy lên cây thứ $i$ , chiều cao cây đó giảm đi $1$ đơn vị.
Sau mỗi lần dùng cưa, cưa phải được sạc lại trước khi dùng tiếp.
Chi phí mỗi lần sạc phụ thuộc vào cây có chỉ số lớn nhất đã bị chặt hoàn toàn (chiều cao bằng $0$ ): nếu chỉ số lớn nhất đó là $i$ , chi phí một lần sạc là $b_{i}$ .
Nếu chưa có cây nào bị chặt hoàn toàn thì không thể sạc cưa.
Cưa được sạc đầy ngay từ đầu (lần dùng đầu tiên không tốn chi phí).

Đã biết rằng $a_{1} = 1$ , $b_{n} = 0$ , dãy $a$ tăng ngặt và dãy $b$ giảm ngặt.

Hãy tính tổng chi phí tối thiểu để chặt sạch toàn bộ $n$ cây.

Dữ liệu vào

Dòng đầu chứa số nguyên $n$ .
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ .
Dòng thứ ba chứa $n$ số nguyên $b_{1}, b_{2}, \dots, b_{n}$ .

Dữ liệu ra

In ra một số nguyên duy nhất — tổng chi phí tối thiểu để chặt sạch toàn bộ cây.

Ràng buộc

$1 \leq n \leq 10^{5}$
$1 \leq a_{i} \leq 10^{9}$ , $0 \leq b_{i} \leq 10^{9}$
$a_{1} = 1$ , $b_{n} = 0$
$a_{1} < a_{2} < \dots < a_{n}$ và $b_{1} > b_{2} > \dots > b_{n}$

Ví dụ

Input	Output	Giải thích
5 1 2 3 4 5 5 4 3 2 0	25	Chặt cây $1$ (chỉ tốn $1$ lần cưa, lần đầu miễn phí). Mọi cây sau đó chặt theo thứ tự $2, 3, 4, 5$ , mỗi cây $i$ tốn $a_{i}$ lần sạc và mỗi lần sạc có giá $b_{i - 1}$ (vì cây có chỉ số lớn nhất đã chặt xong là $i - 1$ ). Tổng: $2 \cdot 5 + 3 \cdot 4 + 4 \cdot 3 + 5 \cdot 2 = 44$ . Có thể làm tốt hơn bằng cách chặt cây $5$ ngay sau cây $1$ : cây $5$ tốn $5 \cdot 5 = 25$ . Sau đó $b_{5} = 0$ nên các cây còn lại miễn phí. Tổng tối ưu là $25$ .
6 1 2 3 10 20 30 6 5 4 3 2 0	138	Chặt cây $1$ miễn phí, rồi tới cây $6$ : $30 \cdot 6 = 180$ ? Không tối ưu. Chiến lược tối ưu là $1 \to 3 \to 6$ : cây $3$ tốn $3 \cdot 6 = 18$ , cây $6$ tốn $30 \cdot 4 = 120$ , sau đó $b_{6} = 0$ nên các cây còn lại miễn phí — tổng $138$ .

Bình luận

Không có bình luận tại thời điểm này.