Trọng số tối đa

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

Thời gian: 1.0s

Bộ nhớ: 256M

Input: bàn phím

Output: màn hình

Tác giả:

huyhau6a2

Dạng bài

Trọng số của một dãy số nguyên là tổng của dãy nhân với số phần tử của dãy. Ví dụ trọng số của dãy $(4,-2,3,1)$ là $6\cdot 4=24$

Cho dãy số nguyên $a=a_1,a_2,\dots,a_n$ . Hãy tách $a$ thành các dãy con (không nhất thiết kề nhau) sao cho tổng trọng số của các dãy con là lớn nhất có thể

Input, Output và Subtasks

Input

Dòng đầu tiên chứa số nguyên dương $n$ ( $n\le 10^5$ )
Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots,a_n$ ( $-10^8\le a_i\le 10^8$ )

Output

Một số nguyên là tổng trọng số lớn nhất tìm được

Subtasks

Subtask 1 $(12\%)$ : $n \le 20$
Subtask 2 $(28\%)$ : $n \le 1000$
Subtask 3 $(60\%)$ : Không có giới hạn gì thêm

Sample 1

Input

6
3 -1 -5 3 -2 6

Output

Bình luận

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