No.949 飲酒プログラミングコンテスト

レベル : / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 63
作問者 : りあんりあん / テスター : butsurizukibutsurizuki
9 ProblemId : 3719 / 出題時の順位表
問題文最終更新日: 2019-12-10 23:17:08

すまない

想定解は Python3 で TLE しました。PyPy3 で提出すると AC できることは確認しています。

問題文

ken さんと koo さんは、2 人でチームを組んで「飲酒競技プログラミングコンテスト (Inshu Competitive Programming Contest; ICPC)」に参加することにしました。

ICPC は $N$ 問の問題からなるコンテストで、以下の行動を何回か行うことでより多くの問題を解くことを目指します。

  • チームメンバーの誰か一人が飲酒をする。そして、まだ解いていない問題を 1 つ選び、その問題を解く。

各チームメンバーには貢献度が決まっており、ken さんが $i$ 回 $(0 \le i \le N)$ 飲酒をした後の貢献度は $A_i$、koo さんが $i$ 回 $(0 \le i \le N)$ 飲酒をした後の貢献度は $B_i$ です。

また各問題には難易度が決まっており、$i$ 番目 $(1 \le i \le N)$ の問題の難易度は $D_i$ です。難易度が $D_i$ の問題は、その時点でのチームメンバーの貢献度の総和が $D_i$ 以上ならば解くことができます。

各チームメンバーの貢献度と各問題の難易度がわかっているとき、最適な戦略を取った場合最大で何問の問題を解けるかを求めてください。

入力

$N$
$A_0 \ A_1 \ \ldots \ A_N$
$B_0 \ B_1 \ \ldots \ B_N$
$D_1 \ D_2 \ \ldots \ D_N$

1 行目に問題の個数を表す整数 $N$ が与えられます。

2 行目に $N+1$ 個の整数が半角スペース区切りで与えられ、その内の $i+1$ 番目 $(0 \le i \le N)$ の整数 $A_i$ は、ken さんが $i$ 回の飲酒をした直後の貢献度の値を表します。

3 行目に $N+1$ 個の整数が半角スペース区切りで与えられ、その内の $i+1$ 番目 $(0 \le i \le N)$ の整数 $B_i$ は、koo さんが $i$ 回の飲酒をした直後の貢献度の値を表します。

4 行目に $N$ 個の整数が半角スペース区切りで与えられ、その内の $i$ 番目 $(1 \le i \le N)$ の整数 $D_i$ は、$i$ 番目の問題の難易度の値を表します。


入力は全部で $4$ 行となり、以下の制約を満たします。

  • 入力は全て整数
  • $1 \le N \le 3{,}000$
  • $-10^5 \le A_i, B_i \le 10^5$
  • $A_{i} \ge A_{i+1}$
  • $B_{i} \ge B_{i+1}$
  • $1 \le D_i \le 2 \times 10^5$

出力

解くことのできる問題数の最大値を出力してください。

サンプル

サンプル1
入力
4
5 3 0 -1 -2
5 4 1 0 -3
5 7 4 8
出力
3

例えば、以下のように行動することにより 3 問の問題を解くことができます。

  • koo さんが飲酒をする。貢献度の和は $5 + 4 = 9$ となる。そして $4$ 番目の問題を解く。
  • ken さんが飲酒をする。貢献度の和は $3 + 4 = 7$ となる。そして $1$ 番目の問題を解く。
  • ken さんが飲酒をする。貢献度の和は $0 + 4 = 4$ となる。そして $3$ 番目の問題を解く。
サンプル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

どちらが飲酒をしてもチームメンバーの貢献度の総和が $1$ より小さくなってしまうため、1 問も解くことができません。

サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。