問題一覧 > 通常問題

No.2694 The Early Bird Catches The Worm

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 126
作問者 : MMMM / テスター : 👑 timitimi hibit_athibit_at mo124121mo124121 ypwwypww
3 ProblemId : 10611 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-03-23 14:45:49

問題文

「早起きは三文の徳」ということわざを知ったMMさんは、これからの $N$ 日間のうち連続する何日かを選んで早起きしようと決意しました。

厳密には、 $1\le L \le R \le N$ を満たす整数 $(L,R)$ の組を1つ選び、 $L$ 日目から $R$ 日目までの $R-L+1$ 日間だけ早起きすることにしました。

MMさんは $i$ 日目 $(1\le i \le N)$ に早起きすることで満足度 $A_i$ を得ます。一方、早起きしなかった場合、その日に得られる満足度は $0$ となります。 MMさんが $i$ 日目に早起きする難易度は $B_i$ で表されます。

MMさんは $j$ 日目 $(L\le j \le R)$ に早起きすると、それまでに早起きした日数と難易度の積、すなわち $(j-L+1)\times B_j$ だけ疲労度が蓄積します。

$N$ 日目を終えた時点での疲労度の合計が $H$ 以下となるように $(L,R)$ の組を1つ選んだとき、MMさんが得られる満足度の総和の最大値を求めてください。

ただし、疲労度の合計が $H$ 以下となる $(L,R)$ の組が存在しない場合は満足度の最大値を $0$ とします。

入力

$N\ H$
$A_1\ \dots\ A_N$
$B_1\ \dots\ B_N$

制約

  • 入力はすべて整数
  • $1\le N \le 2 \times 10^5$
  • $1\le H \le 10^9$
  • $1\le A_i,B_i \le 10^9 (1\le i\le N)$

出力

答えを1行で出力してください。

サンプル

サンプル1
入力
7 22
5 10 15 20 25 30 35
10 5 4 3 2 5 10
出力
75

$(L,R) = (4,6)$ のとき、疲労度は $1\times B_4 + 2\times B_5 + 3\times B_6 = 22$ となり、MMさんは満足度 $A_4 + A_5 + A_6 =75$ を得ます。

疲労度が $22$ 以下となるような $(L,R)$ の組の中では、このとき満足度が最大になります。

なお、$(L,R) = (3,6)$ のとき満足度は $90$ となりますが、疲労度が $1\times B_3 + 2\times B_4 + 3\times B_5 + 4\times B_6 = 36 > 22$ となるため、不適となります。

サンプル2
入力
7 1
5 10 15 20 25 30 35
10 5 4 3 2 5 10
出力
0

MMさんがあまりに朝に弱い場合、1日も早起きすることができません。このときは $0$ を出力します。

サンプル3
入力
7 1000000000
5 10 15 20 25 30 35
10 5 4 3 2 5 10
出力
140

MMさんが朝に極めて強い場合、$1$ 日目から $N$ 日目までずっと早起きし続けることができます。

サンプル4
入力
10 23
3 1 4 1 5 9 2 6 5 3
2 7 1 8 2 8 1 8 2 8
出力
16

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。