문제

n개의 정수로 이루어진 수열이 있다. 이 수열에서 한 정수를 제거하거나, 또는 두 정수를 제거할 수 있다. 한 정수를 제거하는 경우에는 그 정수가 점수가 되고, 두 정수를 제거하는 경우에는 두 정수의 곱이 점수가 된다. 이를 반복하여 수열에 아무 수도 남지 않게 되었을 때, 점수의 총 합의 최대를 구하는 프로그램을 작성하시오.

예를 들어 -1, 5, -3, 5, 1과 같은 수열이 있다고 하자. 먼저 1을 제거하고, 다음으로는 5와 5를 제거하고, 다음에는 -1과 -3을 제거했다고 하자. 이 경우 각각 점수가 1, 25, 3이 되어 총 합이 29가 된다.

# 2036
import sys
input = lambda: sys.stdin.readline().strip()

import heapq

n = int(input())
plus_arr, minus_arr = [], []

for _ in range(n):
    num = int(input())
    if num > 0:
        heapq.heappush(plus_arr, -num)
    else:
        heapq.heappush(minus_arr, num)
        
total = 0

while len(plus_arr) > 1:
    num1 = heapq.heappop(plus_arr)
    if num1 == -1:
        heapq.heappush(plus_arr, num1)
        break
    num2 = heapq.heappop(plus_arr)
    if num2 == -1:
        heapq.heappush(plus_arr, num2)
        total -= num1
        break
    total += (num1 * num2)
    
while len(minus_arr) > 1:
    num1 = heapq.heappop(minus_arr)
    num2 = heapq.heappop(minus_arr)
    total += (num1 * num2)
    
if len(minus_arr) == 1:
    num1 = heapq.heappop(minus_arr)
    total += num1

total -= sum(plus_arr)
    
print(total)

백준 2036 수열의 점수