Page not loading? Try clicking here.
Placeholder

#2498

[고등부] 2025 KOI 1차대회 대비 모의고사 (3주차)

Player-based Team Distribution
Subtask
1s 1024MB

Problems

플레이어 N명이 1개 이상의 팀으로 나누어 게임을 진행하려 한다. 플레이어는 각각 정확히 한 팀에 속해야 한다. i번째 플레이어는 같은 팀에 속한 인원 수와 a_i를 곱한 것만큼의 점수를 얻는다.

팀을 적절히 나누었을 때, 모든 플레이어의 점수의 합의 최댓값을 구해보자.


Input

첫째 줄에 N (1 \leq N \leq 10^5)이 주어진다.

둘째 줄에 N개의 정수가 주어진다. i번째 수는 a_i이다. ( -10^5 \leq a_i \leq 10^5)


Output

첫째 줄에 팀을 적절히 나누었을 때 모든 플레이어들의 점수의 합의 최댓값을 출력한다.


Subtask

# Score Condition
#130

N \le 10

#210

A_i \le 0

#360

추가 제약 조건 없음


Example 

4
5 -9 3 7
36

하나의 바구니에 5, 3, 7 값어치를 갖는 달걀을 담고 다른 한 바구니에 -9를 담는다.

이때 값어치는 (5 + 3 + 7) * 3 - 9 = 45 - 9 = 36 이고 이보다 더 큰 값을 얻을 수 없다.

You must sign in to write code.