問題一覧 > 通常問題

No.2546 Many Arithmetic Sequences

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 22
作問者 : ShirotsumeShirotsume / テスター : 👑 NachiaNachia kaichou243kaichou243
1 ProblemId : 9380 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-11-15 16:42:33

問題文

$N$ 個の等差数列があります。$i$ 個目の等差数列は初項 $A_i$ 、公差 $D_i$ 、項数 $10^{100}$ です。

長さ $N$、総和 $M$ の非負整数列 $X = (X_1, X_2, \dots, X_N)$ に対して、$X$ のスコア $f(X)$ を次の通り定めます。

  • $\displaystyle f(X) = \sum_{i = 1}^{N}$ （ $i$ 個目の等差数列の先頭 $X_i$ 項の総和）

ただし、先頭 $0$ 項の総和は $0$ であると定めます。

長さ $N$、総和 $M$ の非負整数列 $X$ を自由に選べるとき、$f(X)$ の値として考えられる最大値を求めてください。

制約

  • 入力は全て整数
  • $2 \leq N \leq 3 \times 10^5$
  • $1 \leq M \leq 3 \times 10^5$
  • $-10^7 \leq A_i, D_i \leq 10^7$

入力

入力は標準入力から以下の形式で与えられる。

$N$ $M$
$A_1$ $D_1$
$\vdots$
$A_N$ $D_N$

出力

$f(X)$ の最大値を出力せよ。この問題の制約下で、答えの絶対値は $2^{63}$ 未満であることが示せる。

サンプル

サンプル1
入力
3 5
1 2
-8 5
13 -7
出力
29

$3$ つの等差数列 $(1, 3, 5, \dots), (-8, -3, 2, \dots), (13, 6, -1, \dots)$ があります。

$X = (4, 0, 1)$ としたとき、スコアは $29$ となり、これが最適です。

サンプル2
入力
2 10
-100 -100
-10 0
出力
-100

$2$ つの等差数列 $(-100, -200, -300, \dots), (-10, -10, -10, \dots)$ があります。

$X = (0, 10)$ としたとき、スコアは $-100$ となり、これが最適です。スコアは負の値を取りうることに注意してください。

サンプル3
入力
5 2000
4005698 -1849641
3217860 -4274311
9504793 -3809644
-1590549 2314
2581917 -3604118
出力
1454884836

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