No.107 モンスター

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 85
作問者 : nmnmnmnmnmnmnmnmnmnmnmnmnmnm

2 ProblemId : 102 / 出題時の順位表

問題文

$N$匹のモンスターがいる。
モンスターには$2$種類ある。
悪いモンスターと良いモンスターの$2$種類である。
悪いモンスターとは$1$匹に対し$1$回戦わないといけない。
戦うと体力が減りレベルが$1$上がる。
レベルが1上がると最大体力が$100$上がる。
もし体力が減って$0$以下になればそこで終了する。
良いモンスターは$1$匹につき$1$回だけ体力を回復してくれる。
ただし、回復する体力は最大体力を越えることはない。

自分の最初の体力は$100$で最大体力も$100$である。
悪いモンスターをすべて倒したい。
また、最後に残った体力をできるだけ多くしたい。
モンスターには自由な順番で出会える。
最後までどれだけの体力を残せるだろうか?
どのようにしても途中で体力が$0$以下になる場合は$0$を答えとする。

ただし、良いモンスターを倒すことは出来ない。

入力

$N$
$D_1\ D_2\ ... D_{N}$

$N$はモンスターの総数。$1\le N \le 16$。($N$は正の整数。)
$D_i$は$i$番目のモンスターの情報。
$D_i$が正の数であれば良いモンスターで|$D_i$|だけ回復してくれる。
$D_i$が負の数であれば悪いモンスターで倒すのに|$D_i$|だけ体力を使う。
$-1600 \le Di < 0、0 < Di \le 1600$。($D_i$は$0$以外の整数。)

出力

最後の時点での体力の最大値を1行で出力せよ。
どうがんばっても途中で体力が0以下になる場合には0を1行で出力せよ。
最後に改行を忘れずに。

サンプル

サンプル1
入力
3
-90 50 50
出力
110

最初に1番目の悪いモンスターと戦う。
体力が10になり、最大体力が200になる。
2,3番目の2匹の良いモンスターに体力を50ずつ回復してもらう。
最終的な体力は110になる。
もし、先に回復を行っても体力は最大体力の100より増えない。
この場合、最後に戦うと最終的な体力は10になる。

サンプル2
入力
4
-90 230 -120 120
出力
240

1番目の悪いモンスターと戦う。
体力は10、最大体力は200になる。
4番目の良いモンスターに回復してもらう。
体力は130になる。
3番目の悪いモンスターと戦う。
体力は10、最大体力は300になる。
2番目の良いモンスターに回復してもらう。
体力は240になる。

サンプル3
入力
4
-10 -300 100 100
出力
0

1番目の悪いモンスターと戦うと体力が90に減り最大体力は200になる。
3,4番目の良いモンスターに体力200まで回復してもらうことはできる。
しかし、どうがんばっても2番目の悪いモンスターと戦うと体力は0以下になる。

サンプル4
入力
4
-40 -60 210 -110
出力
50

2番目の悪いモンスターと戦う。
体力は40、最大体力は200になる。
3番目の良いモンスターに回復してもらう。
最大体力を超えられないので体力は200になる。
1,4番目の悪いモンスターと戦う。
体力は50になる。

提出ページヘ