Trung bình cộng (THTB ĐN 2023)

Điểm: 900 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 256M

Input: TBCONG.inp

Output: TBCONG.out

Tác giả:

Sunlight

Dạng bài

Cho số nguyên $n$ và dãy gồm $n$ số nguyên $a_1, a_2,\dots,a_n$ . Tìm cách xóa đi tối đa 2 dãy con liên tiếp không cắt nhau của dãy đó để các phần tử còn lại có trung bình cộng lớn nhất.

Note: Không có trung bình cộng của dãy rỗng

Input, Output và Subtasks

Input: (TBCONG.inp)

Dòng đầu tiên chứa số nguyên dương $n$ ( $1\le n\le 10^6$ ) là số phần tử của dãy số
Dòng thứ hai gồm $n$ số nguyên $a_1,a_2,\dots,a_n$ ( $|a_i|\le 10^9$ ) là các phần tử của dãy

Output: (TBCONG.out)

Số nguyên duy nhất là phần nguyên trung bình cộng của các phần tử còn lại

Subtasks

Subtask 1 $(30\%)$ : $n\le 10^3$
Subtask 2 $(30\%)$ : $n\le 10^5$
Subtask 3 $(40\%)$ : Không có ràng buộc gì thêm

Sample 1

Input (TBCONG.inp)

5
2 5 5 1 3

Output (TBCONG.out)

Note

Xóa đi 2 dãy $[1,1]$ và $[4,5]$

Bình luận

Không có bình luận nào.