TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的!雖然想像得出來也不一定可以就是了

User's AC Ratio

92.5% (49/53)

Submission's AC Ratio

71.8% (89/124)

Tags

Description

經過了一個似乎平安的晚上...
「喔膩醬...」你身邊的祈說道
「我還不知道喔膩醬叫什麼名字耶」
「啊...我叫小志(jizzin)」
「恩!還有跟喔膩醬說喔,我的姓是「天」喔,不過喔膩醬直接叫我名字就好」
祈繼續說到,
「那個,感謝喔膩醬救了我一命,我決定給喔膩醬一個特別的獎勵喔」
「喔喔喔!這個蘿莉果然沒有白撿回來!我的內心,內心的某個深處絕醒了啊啊啊啊!!」你暗爽著。
「那你到底要給我什麼獎勵呢?」你心中早已幻想過數種情況。
「呵呵,那就要看我有多喜歡喔膩醬囉。」
「為了男人的尊嚴,我...我一定要攻略下這隻小蘿莉。」
因此你決定利用這段時間好好增加對祈的好感度
你想到了有N種事情可以做(如:跟她說故事、餵她吃棒棒糖或是一起做體操等等),第i種事情可以增加好感度a_i 。

當然,做太多事也是會累的,因此當你第i種事情放在第j個來做時,你實際上對祈的好感度只會增加a_i −j。
你要選那些事情來做並要如何決定順序,才能增加最多好感度呢?

Input Format

第一行有一個正整數T,代表有T筆測資。
每個測資的第一行有一個正整數N代表有多少種事情可以做,第二行有N個正整數,第i個數代表a_i ,即做第i件事情的好感度。

Output Format

對於每筆測資輸出一行,包含一個數字,代表好感度增加的最大值。

Sample Input 1

3
5
1 2 3 4 5
5
1 1 1 1 1
5
1 4 2 7 5

Sample Output 1

6
0
10

Hints

對於範例測資的第一筆輸入,你可以先做第4件事,獲得4−1=3的好感度,再做第5件事,獲得5−2=3的好感度,而得到最大值6。
第二筆輸入,你乾脆不要做任何事。
第三筆輸入你可以依序作第2,5,4件事。

對於所有測試資料 : ai≤104
測資組A : T≤20,N≤10
測資組B : T≤20,N≤50
測資組C : T≤20,N≤3000
測資組D : T≤20,N≤105

Problem Source

Step5

Subtasks

No. Testdata Range Score
1 0~1 20
2 2~3 20
3 4~7 45
4 8~9 15

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 2
3 1000 65536 262144 2
4 1000 65536 262144 3
5 1000 65536 262144 3
6 1000 65536 262144 3
7 1000 65536 262144 3
8 1000 65536 262144 4
9 1000 65536 262144 4