Bộ ba số (THT C2 Đà Nẵng 2022)

Xem PDF
Tác giả:
Small
Dạng bài
Đ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 6
Output 
35
Note

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


  • 0
    nguyenphuckhang    12:45 p.m. 22 Tháng 5, 2023

    Bài này dùng Min và Max segment tree AC được


    • 0
      trieunguyen_a1    11:11 p.m. 17 Tháng 7, 2023

      Hình như hơi dư nhỉ


      • 0
        nguyenphuckhang    6:56 p.m. 18 Tháng 7, 2023

        tui cũm nghĩ vậy, ông có cách nào tối ưu hơn k. Tại cách tui làm hơi dài


        • -1
          trieunguyen_a1    1:08 p.m. 19 Tháng 7, 2023

          Nhiều cách ngắn mà cách đơn giản nhất là :
          Với từng i : tìm 2 số lớn nhất trong đoạn [1 , i - 1] gọi là x , y sao cho : x <= y , thì ông lấy max
          của res với 3 * y + 2 * x - 5 * a[i] . Xong rồi ông xét a[i] để làm mới 2 biến x , y để cập nhất từ đoạn [1 , i - 1] -> [1 , i] :
          Nếu a[i] >= y , x = y , y = a[i]
          ngược lại x = max(x , a[i])

      2 bình luận nữa