a139. TOI 2023/12 潛力組：聚寶盆

題目描述

你擁有 N 種寶物，每種一件，單件價值可能是負數。第一天白天可以選擇若干種寶物放進聚寶盆。此後每個晚上，盆內每種仍然存在的寶物各增加一件，並不是把數量翻倍。

從第二天白天起，每天必須選擇盆內的一種寶物，把該種類全部取出。取出的種類不再增加；持續操作直到盆中沒有寶物。若某種類是第 k 個被取出的，就能取出 k+1 件。可以一開始就不放入任何寶物。

請決定放入的種類與取出順序，使最後取出寶物的價值總和最大。

輸入格式

第一行輸入 N，1 ≤ N ≤ 100000。 第二行輸入 N 個整數，代表各種寶物的單件價值，每個值介於 −2000 與 2000 之間。即使價值相同，仍視為不同種類。

輸出格式

輸出最高可取得的總價值。答案可能超過 32 位元整數範圍。

來源

TOI 2023 年 12 月潛力組〈聚寶盆〉。依官方題意重新撰寫，範例與測資另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202312/TreasureBowl.pdf