Tìm tổng lớn nhất với phép toán xoá

Xem PDF

Điểm: 400 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

-Ta có một số \(T\) ban đầu có giá trị bằng \(0\)

-Cho một mảng \(a\) gồm \(n\) phần tử và một phép toán như sau:

  • Chọn phần tử \(a_k(1\le k\le n)\) bất kỳ sau đó xoá đi tất cả các phần tử có giá trị \(a_k,a_k+1,a_k-1\) và cộng \(a_k\) vào \(T\)

Yêu cầu: Hãy thực hiện phép toán trên với một số lần tuỳ ý sao cho ta thu được giá trị \(T\) lớn nhất có thể. Giá trị \(T\) lớn nhất đó chính là kết quả cần tìm

Input

  • Dòng thứ nhất chứa số \(n(1\le n\le 10^5)\)

  • Dòng thứ hai chứa \(n\) số nguyên \(1\le a_i\le 10^5\) với \(1\le i\le n\)

Output

  • In ra giá trị cần tìm

Example

Test 1

Input
3
3 2 1
Output
4
Note
  • Đầu tiên: Ta chọn \(a[1]=3\) và sao đó xoá đi \(a[2]\) . Cộng \(a[1]\) vào \(T\) ta được \(T=3\). Lúc này mảng chỉ còn một phần tử có giá trị là \(1\). Và cộng nốt vào \(T\) ta được \(T=4\)

Bình luận


  • 7
    trumktx    9:48 p.m. 9 Tháng 5, 2021

    Viết đề không rõ yêu cầu ạ.

    Đề ghi cộng ak vào T mà trên các test chấm thì phải cộng tất cả các giá trị ak vào T.

    1 phản hồi

    • 1
      tien_noob    7:19 p.m. 8 Tháng 5, 2021

      Bài này bị trùng ad ơi, cùng cách làm chỉ là thay problem statement
      https://lqdoj.edu.vn/problem/reward


      • -11
        ekhoavvdd    4:55 p.m. 8 Tháng 5, 2021

        Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


        • -5
          ekhoavvdd    4:48 p.m. 8 Tháng 5, 2021

          Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.