問題一覧 > 通常問題

No.2694 The Early Bird Catches The Worm

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

問題文

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

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

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

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

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

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

入力

N HN\ H
A1 … ANA_1\ \dots\ A_N
B1 … BNB_1\ \dots\ B_N

制約

  • 入力はすべて整数
  • 1≤N≤2×1051\le N \le 2 \times 10^5
  • 1≤H≤1091\le H \le 10^9
  • 1≤Ai,Bi≤109(1≤i≤N)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)(L,R) = (4,6) のとき、疲労度は 1×B4+2×B5+3×B6=221\times B_4 + 2\times B_5 + 3\times B_6 = 22 となり、MMさんは満足度 A4+A5+A6=75A_4 + A_5 + A_6 =75 を得ます。

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

なお、(L,R)=(3,6)(L,R) = (3,6) のとき満足度は 9090 となりますが、疲労度が 1×B3+2×B4+3×B5+4×B6=36>221\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日も早起きすることができません。このときは 00 を出力します。

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

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

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