時間制限:$2.0sec$ / メモリ制限:$256MB$
こたまねぎ君達は航海のために船を買ったのですが、前日に船が水に浮かばない欠陥船だという事がわかってしまいました。
詐欺に遭ってしまった彼らはどうにかして大きな船を調達したいのですが、もうお金がありません。
そこで、この欠陥船をのこぎりで2つに切って、水に浮かぶようにするというアイデアを採用することになりました。
あなたの仕事は、できるだけ多くの物資を乗せるために、切った船の大きさが最大になるような切り方を提案する事です。
欠陥船はn等分でき、それぞれの部分$i$について浮力は$Ai$です。
切った後の船の浮力の和が0以上の時、船は浮きます。
追記 船を三つ以上に切ることはできません。
$1 ≦ i ≦ n$を満たす$i$について、
入力は以下の形式で標準入力から与えられる。
n
A1 A2 A3 … An
切った後の船の長さを出力してください。 ただし、どう切っても水に浮かない船が出来上がる場合は、$-1$を出力してください。
4
1 -1 2 -3
3
3番目と4番目の境目で切ると、1~3番目の船が$1+(-1)+2=2$で水に浮くので、これが最大の船の大きさとなります。
7
1 2 3 -1000 3 2 1
3
1番目から3番目または5番目から7番目までを新しい船とすると最大の大きさとなります。
10
-1 -2 -3 -4 -5 -6 -7 -8 -9 -10
-1
もしかして:詰み状態