플레이어 기반 팀 분배

면접 대비

시간 제한1초메모리 제한1024 MB

요약

N명의 선수를 팀으로 나눈다. 크기 s인 팀에 속한 값 a_i인 선수는 s*a_i점을 얻을 때, 전체 점수의 최댓값을 구한다.

문제

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

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

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

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

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