Vasya và Đồng Nấm

Điểm: 6,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

Assembly, C#, C++, D, Dart, Go, Groovy, Java, Javascript, Kotlin, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Ruby, Rust, Scratch, Typescript, Zig

Cho một lưới hình chữ nhật gồm $2$ hàng và $n$ cột. Mỗi ô của lưới có một giá trị tốc độ mọc nấm — số gam nấm mọc thêm trong mỗi phút.

Vasya bắt đầu ở ô góc trên bên trái (hàng $1$ , cột $1$ ) tại thời điểm $0$ . Mỗi phút, Vasya bắt buộc phải di chuyển sang một ô kề cạnh (chung cạnh). Vasya không được phép đứng yên, không được đi ra khỏi lưới, và phải đi qua mỗi ô đúng một lần.

Khi Vasya bước vào một ô tại thời điểm $t$ , toàn bộ nấm trong ô đó được thu hoạch ngay lập tức. Tại thời điểm $t$ , khối lượng nấm trong một ô có tốc độ mọc $g$ chính bằng $t \cdot g$ (gam). Lúc đầu mọi ô đều có $0$ gam nấm; cây nấm chỉ tích lũy theo thời gian từ lúc $0$ .

Hãy tính tổng khối lượng nấm lớn nhất mà Vasya có thể thu được sau khi đi qua hết toàn bộ $2 n$ ô. Vasya không cần phải quay lại ô xuất phát.

Dữ liệu vào

Dòng đầu chứa một số nguyên $n$ — số cột của lưới.
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ — tốc độ mọc nấm ở các ô của hàng thứ nhất.
Dòng thứ ba chứa $n$ số nguyên $b_{1}, b_{2}, \dots, b_{n}$ — tốc độ mọc nấm ở các ô của hàng thứ hai.

Dữ liệu ra

Một số nguyên duy nhất — tổng khối lượng nấm lớn nhất Vasya có thể thu được.

Ràng buộc

$1 \leq n \leq 3 \cdot 10^{5}$
$1 \leq a_{i}, b_{i} \leq 10^{6}$

Ví dụ

Input	Output	Giải thích
3 1 2 3 6 5 4	70	Một lộ trình tối ưu: $(1, 1) \to (1, 2) \to (1, 3) \to (2, 3) \to (2, 2) \to (2, 1)$ . Khối lượng thu được: $0 \cdot 1 + 1 \cdot 2 + 2 \cdot 3 + 3 \cdot 4 + 4 \cdot 5 + 5 \cdot 6 = 70$ .
3 1 1000 10000 10 100 100000	543210	Một lộ trình tối ưu: $(1, 1) \to (2, 1) \to (2, 2) \to (1, 2) \to (1, 3) \to (2, 3)$ . Khối lượng thu được: $0 \cdot 1 + 1 \cdot 10 + 2 \cdot 100 + 3 \cdot 1000 + 4 \cdot 10000 + 5 \cdot 100000 = 543210$ .

Bình luận

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