No.2694 The Early Bird Catches The Worm
タグ : / 解いたユーザー数 128
作問者 :
MM
/ テスター :
👑 
hibit_at
mo124121
ypww
問題文
「早起きは三文の徳」ということわざを知った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もしくは右上の雲マークをクリックしてアカウントを作成してください。