B - JOI 悪徳商店
問題文
IOI 王国には，悪質な販売で有名な「JOI 商店」がある．JOI 商店は 1 種類の商品しか売っておらず，毎日値段が変動する．既に今後 $N$ 日間の値段は公開されており，今日から数えて $i$ 日目(以後，$i$ 日目と記す)の商品の値段は $A_i$ 円である．
JOI 商店では，1 日当たり 2 個以上の商品を買うことはできず，すなわち各日について「1個商品を買う」「買わない」という 2 種類の選択のうちいずれかしかできない．また，2 日以上連続で商品を買う場合は，次表の通りに割引あるいは割増される．（連続購入日数は，買わなかった日があればリセットされることに注意せよ．）ただし，10 割引以上の場合は，商品を買うと逆にお金がもらえることを意味する．
| 連続購入日数 | 発生する割引／割増 |
|---|---|
| 連続購入 1 日目 | 何も起こらない |
| 連続購入 2 日目 | 7 割引（その日の商品が 0.3 倍の価格で買える） |
| 連続購入 3 日目 | 7 割増（その日の商品が 1.7 倍の価格で買える） |
| 連続購入 4 日目 | 14 割引（その日の商品が -0.4 倍の価格で買える） |
| 連続購入 5 日目 | 14 割増（その日の商品が 2.4 倍の価格で買える） |
| 連続購入 6 日目 | 21 割引（その日の商品が -1.1 倍の価格で買える） |
| 連続購入 7 日目 | 21 割増（その日の商品が 3.1 倍の価格で買える） |
| 連続購入 8 日目 | 28 割引（その日の商品が -1.8 倍の価格で買える） |
| 連続購入 9 日目 | 28 割増（その日の商品が 3.8 倍の価格で買える） |
| 連続購入 10 日目 | 35 割引（その日の商品が -2.5 倍の価格で買える） |
| $\vdots$ | $\vdots$ |
E869120 君は JOI 商店に $N$ 日間通い，金儲けに挑戦することにした．彼は最大で何円の利益を得ることができるか．ただし，どの日も商品を買わなかった場合の利益は $0$ 円であり，利益は負になることもある．
制約
- $1 \leq T \leq 10$
- $1 \leq N \leq 50$
- $10 \leq A_i \leq 100000$
- $A_i$ は $10$ の倍数である．
- 入力はすべて整数である．
この課題は，3 個の小課題から成る．
| 小課題 | 得点 | 内容 | 入力データ番号 | $T$ の値 |
|---|---|---|---|---|
| 0 | - | サンプルテストケース | #0 | - |
| 1 | 15 | $A_1 = A_2 = A_3 = ... = A_N$ | #1 | 5 |
| 2 | 35 | $N ≤ 16$ | #2 | 10 |
| 3 | 50 | 追加の制約はない． | #3 | 10 |
入力
各入力データ について,以下の形式で入力が与えられる.
$T$
($1$ 個目のテストケースの情報)
($2$ 個目のテストケースの情報)
...
($T$ 個目のテストケースの情報)
各テストケース について,以下の形式で入力が与えられる.
- 1 行目に，整数 $N$ が与えられる.
- 2 行目に，整数 $A_1, A_2, A_3, ... , A_N$ が空白区切りで与えられる.
出力
$T$ 行に渡って出力せよ．
$i$ 行目には，$i$ 個目のテストケースにおける答えを 整数形式 で出力せよ．
2
7
100 100 200 400 800 1600 10000
6
100 100 100 100 100 100
6640
0
この入力データには，$2$ 個のテストケースが存在する．($T=2$ である．)
$1$ 個目のテストケースに関しては，今日から $7$ 日間の値段データは次表の通りである．
| $1$ 日目 | $2$ 日目 | $3$ 日目 | $4$ 日目 | $5$ 日目 | $6$ 日目 | $7$ 日目 |
|---|---|---|---|---|---|---|
| $100$ 円 | $100$ 円 | $200$ 円 | $400$ 円 | $800$ 円 | $1600$ 円 | $10000$ 円 |
例えば，$2, 3, 4, 5, 6, 7$ 日目に商品を買い，$1$ 日目に買わない場合，各日に払う金額は次表の通りとなる．そのとき，払う金額の合計は $100 + 60 + 680 - 320 + 3840 - 11000 = -6640$ 円となり，$E869120$ 君は $6640$ 円の利益を得ることができる．$6641$ 円以上の利益を得る方法は存在しない．
| 日付 | 連続購入日数 | 割引／割増 | 払う金額 |
|---|---|---|---|
| $1$ 日目 | - | - | - |
| $2$ 日目 | 連続購入 $1$ 日目 | 通常通り | $100$ 円 |
| $3$ 日目 | 連続購入 $2$ 日目 | $7$ 割引 | $60$ 円 |
| $4$ 日目 | 連続購入 $3$ 日目 | $7$ 割増 | $680$ 円 |
| $5$ 日目 | 連続購入 $4$ 日目 | $14$ 割引 | $-320$ 円 |
| $6$ 日目 | 連続購入 $5$ 日目 | $14$ 割増 | $3840$ 円 |
| $7$ 日目 | 連続購入 $6$ 日目 | $21$ 割引 | $-11000$ 円 |
$2$ 個目のテストケースに関しては，$1$ 円以上の利益を得る方法は存在しない．また，どの日も商品を買わないことによって利益 $0$ 円が達成できるため，最大の利益は $0$ 円となる．したがって，$0$ と出力すれば正解となる．