R00768
수 묶기
골드 IV레이팅
의견: 0
설명
정수 수열이 주어진다. 수열의 수를 두 개씩 묶을 수 있다. 묶인 두 수는 곱한 값으로, 묶이지 않은 수는 그 수 그대로 합산된다. 각 수는 정확히 한 번씩만 사용해야 한다(묶이거나, 혼자이거나).
예를 들어 \(\{-3, -8, 2, 1, 3, 6\}\)에서 \((-3) \times (-8)\)과 \(3 \times 6\)을 묶고 \(2, 1\)을 그대로 두면 \(24 + 18 + 2 + 1 = 45\)가 된다.
수열의 합이 최대가 되도록 수를 묶었을 때의 합을 구하여라.
제약
\(1 \le N \le 10\,000\), 각 수의 절댓값은 \(1\,000\) 이하.
입력 형식
첫째 줄에 수열의 크기 \(N\)이 주어진다. 둘째 줄부터 \(N\)개의 줄에 수열의 각 수가 주어진다.
출력 형식
만들 수 있는 합의 최댓값을 출력한다.
예제 1
입력
6
-3
-8
2
1
3
6
출력
45
설명
(-3)×(-8) + 3×6 + 2 + 1 = 24 + 18 + 3 = 45.
예제 2
입력
3
-1
0
1
출력
1
설명
(-1)×0 + 1 = 1.
문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
수 묶기
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
수 묶기
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기