No.949 飲酒プログラミングコンテスト
タグ : / 解いたユーザー数 84
作問者 :

すまない
想定解は Python3 で TLE しました。PyPy3 で提出すると AC できることは確認しています。
問題文
ken さんと koo さんは、2 人でチームを組んで「飲酒競技プログラミングコンテスト (Inshu Competitive Programming Contest; ICPC)」に参加することにしました。
ICPC は
- チームメンバーの誰か一人が飲酒をする。そして、まだ解いていない問題を 1 つ選び、その問題を解く。
各チームメンバーには貢献度が決まっており、ken さんが
また各問題には難易度が決まっており、
各チームメンバーの貢献度と各問題の難易度がわかっているとき、最適な戦略を取った場合最大で何問の問題を解けるかを求めてください。
入力
1 行目に問題の個数を表す整数
2 行目に
3 行目に
4 行目に
入力は全部で
- 入力は全て整数
出力
解くことのできる問題数の最大値を出力してください。
サンプル
サンプル1
入力
4 5 3 0 -1 -2 5 4 1 0 -3 5 7 4 8
出力
3
例えば、以下のように行動することにより 3 問の問題を解くことができます。
- koo さんが飲酒をする。貢献度の和は
となる。そして 番目の問題を解く。 - ken さんが飲酒をする。貢献度の和は
となる。そして 番目の問題を解く。 - ken さんが飲酒をする。貢献度の和は
となる。そして 番目の問題を解く。
サンプル2
入力
5 100 0 -100 -200 -300 -400 8 7 6 5 4 3 5 6 7 8 9
出力
5
毎回 koo さんが飲酒をすることにより、全ての問題を解くことができます。
サンプル3
入力
1 1000 -1000 1000 -1000 1
出力
0
どちらが飲酒をしてもチームメンバーの貢献度の総和が
サンプル4
入力
8 34 8 8 -31 -32 -52 -54 -60 -62 87 71 46 42 8 -2 -35 -41 -52 53 25 15 36 82 79 58 36
出力
6
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。