Bộ ba số (THT C2 Đà Nẵng 2022)
Xem PDF
Điểm:
200
Thời gian:
1.0s
Bộ nhớ:
500M
Input:
BOBASO.INP
Output:
BOBASO.OUT
Cho dãy gồm \(N (1 \le N \le 10^5)\) số nguyên \(A_1, A_2, ... , A_N (0 < A_i \le 10^5)\)
Với bộ ba số \((i,j, k)\) trong đó \(1 \le i < j < k \le n\) hãy tìm giá trị \(S = 3A_i + 2A_j − 5A_k\) sao cho \(S\) đạt
giá trị lớn nhất.
Input
Đọc từ file văn bản BOBASO.INP gồm hai dòng:
- Dòng đầu tiên chứa số nguyên \(N\).
- Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, ... , A_N\) giữa các số cách nhau một khoảng trắng.
Output
- Ghi ra file văn bản BOBASO.OUT một số duy nhất là số \(S\) lớn nhất tìm được.
Scoring
- Subtask \(1\) (\(20\%\) số điểm): \(N \le 100\)
- Subtask \(2\) (\(40\%\) số điểm): \(N \le 5.10^3\)
- Subtask \(3\) (\(40\%\) số điểm): \(N \le 10^5\)
Example
Test 1
Input
10
4 9 7 9 4 3 2 9 15 6Output
35Note
3 giá trị số cần tìm để S đạt giá trị lớn nhất lần lượt là 9, 9 và 2 nằm ở 3 vị trí là 2, 4 và 7
Bình luận
Bài này dùng Min và Max segment tree AC được
Dạ ai có hint bài này ko ạ chứ em mới tự học tin còn quá gà mờ môn này, em cảm ơn nhiều ạ 😢
n<=10^5 mà có test n>10^5 hmm