trang chủ / bài tập / maxtriple

Bộ ba tối ưu

Cho dãy số nguyên $a_{1}, a_{2}, \dots, a_{n}$ và ba số nguyên $p$ , $q$ , $r$ .

Hãy tìm giá trị lớn nhất của biểu thức

$p \cdot a_{i} + q \cdot a_{j} + r \cdot a_{k}$

trên mọi bộ ba chỉ số $(i, j, k)$ thoả mãn $1 \leq i \leq j \leq k \leq n$ .

Ba chỉ số không nhất thiết phải phân biệt: hoàn toàn có thể chọn $i = j = k$ . Giá trị lớn nhất tìm được có thể là số âm.

Dữ liệu vào

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

Dữ liệu ra

Một số nguyên duy nhất là giá trị lớn nhất của $p \cdot a_{i} + q \cdot a_{j} + r \cdot a_{k}$ với $1 \leq i \leq j \leq k \leq n$ .

Ràng buộc

$1 \leq n \leq 10^{5}$
$- 10^{9} \leq p, q, r \leq 10^{9}$
$- 10^{9} \leq a_{i} \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
5 1 2 3 1 2 3 4 5	30	Chọn $i = j = k = 5$ , được $1 \cdot 5 + 2 \cdot 5 + 3 \cdot 5 = 30$ .
5 1 2 -3 -1 -2 -3 -4 -5	12	Chọn $i = j = 1$ và $k = 5$ , được $1 \cdot (- 1) + 2 \cdot (- 1) + (- 3) \cdot (- 5) = 12$ . Mọi giá trị $a_{i}$ đều âm nhưng đáp số vẫn dương nhờ $r < 0$ .
3 -2 3 -2 1 2 1	2	Chọn $i = 1$ , $j = 2$ , $k = 3$ , được $- 2 \cdot 1 + 3 \cdot 2 + (- 2) \cdot 1 = 2$ .

Bình luận

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

Nộp bài giải

Danh sách bài nộp Bài nộp tốt nhất

Điểm 4,00một phần

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

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

Đầu vào stdin

Kết quả của bạn stdout

Dạng bài

Chưa phân loạ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