Trên dãy số nguyên 𝑎1, 𝑎2, … , 𝑎𝑛 và với hai số nguyên 𝑤1 và 𝑤2, ta định nghĩa một bộ năm chỉ số 1 ≤ 𝑖1 < 𝑖2 < ⋯ < 𝑖5 ≤ 𝑛 được gọi là một bộ năm và có trọng số được tính bằng: (𝑤1 × 𝑎𝑖1 ) + (𝑤2 × 𝑎𝑖2 ) + 𝑎i3 + (𝑤2 × 𝑎𝑖4 ) + (𝑤1 × 𝑎𝑖5 ). Ví dụ, trên dãy gồm 7 số nguyên 2, 8, 1, 9, 1, −1, 8 và 𝑤1 = 1, 𝑤2 = −1 thì bộ năm chỉ số 2, 3, 4, 6, 7 là một bộ năm và có trọng số bằng (1 × 8) + (−1 × 1) + 9 + (−1 × (−1)) + (1 × 8) = 25, đây cũng là bộ năm có trọng số lớn nhất trong tất cả các bộ năm.
Yêu cầu: Cho dãy số nguyên 𝑎1, 𝑎2, … , 𝑎𝑛 và hai số nguyên 𝑤1 và 𝑤2. Hãy tìm bộ năm có trọng số lớn nhất.
Dữ liệu:
- Dòng đầu chứa ba số nguyên 𝑛, 𝑤1, 𝑤2 (𝑛 ≥ 5; |𝑤1 |, |𝑤2 | ≤ 100);
- Dòng thứ hai chứa 𝑛 số nguyên 𝑎1, 𝑎2, … , 𝑎𝑛 (|𝑎𝑖 | ≤ 109 với 𝑖 = 1, 2, … , 𝑛).
Kết quả:
Ghi ra một số nguyên là trọng số của bộ năm lớn nhất tìm được.
Input
7 1 -1
2 8 1 9 1 -1 8
Output
25
Input
7 0 0
2 8 1 9 1 -1 8
Output
9
Ràng buộc:
- Có 20% số lượng test thỏa mãn điều kiện: 𝑛 ≤ 100;
- Có thêm 20% số lượng test khác thỏa mãn điều kiện: 𝑛 ≤ 105 ; 𝑤1 = 𝑤2 = 0;
- Có thêm 20% số lượng test khác thỏa mãn điều kiện: 𝑛 ≤ 5000; 𝑤1 = 0; 𝑤2 < 0;
- Có thêm 20% số lượng test khác thỏa mãn điều kiện: 𝑛 ≤ 105 ; 𝑤1 = 0; 𝑤2 < 0;
- Có 20% số lượng test còn lại thỏa mãn điều kiện: 𝑛 ≤ 105 .
Nguồn: 3D 20162017