Bài 3. Dãy số (HSG THPT TP. Cần Thơ 2026)

Xem dạng PDF

Gửi bài giải

Điểm: 1,00 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Tác giả:
Nguồn bài:
HSG THPT TP. Cần Thơ 2026
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho một dãy số ~A~ gồm ~n~ phần tử số nguyên có dạng ~a_1, a_2, \ldots, a_n~. Gọi ~W~ là tổng giá trị của ~n - 1~ phần tử được chọn ra trong ~A~. Mỗi lần chọn một phần tử trong hai phần tử đầu tiên và thực hiện theo quy tắc sau:

• Nếu chọn ~a_1~ thì ~W = W + a_1~, sau đó lấy ~a_1~ ra khỏi dãy thì phần tử ~a_2~ lúc này là ~a_1~, phần tử ~a_3~ là ~a_2, \ldots~

• Ngược lại, nếu chọn ~a_2~ thì ~W = W - a_2~, sau đó lấy ~a_2~ ra khỏi dãy thì phần tử ~a_3~ lúc này là ~a_2, \ldots~

Yêu cầu: Hãy lặp lại quy tắc trên một cách tối ưu, xác định giá trị ~W~ lớn nhất khi chọn ra đúng ~n - 1~ phần tử.

Dữ liệu vào

Gồm hai dòng:

  • Dòng đầu tiên ghi số ~n (2 \le n \le 10^5)~.
  • Dòng tiếp theo ghi các số ~a_i (|a_i| \le 10^4)~, mỗi số cách nhau bởi một dấu cách.

Kết quả

Một số nguyên là kết quả tìm được.

Ví dụ

Input 1

4
1 2 -3 2

Output 1

6

Thứ tự chọn tối ưu như sau: ~W = 1 - (-3) + 2 = 6~.

Ràng buộc

  • 30% số test tương ứng với số điểm có ~a_i > 0~.
  • 20% số test tương ứng với số điểm có ~n \le 15~.
  • 50% số test còn lại không ràng buộc gì thêm.

Chương trình đọc dữ liệu từ bàn phím (stdin) và ghi kết quả ra màn hình (stdout).


Đang tải...