No.2546 Many Arithmetic Sequences
タグ : / 解いたユーザー数 22
作問者 :
Nachia
Problem Statement
There are $N$ arithmetic sequences. The $i$-th arithmetic sequence has first term $A_i$, common difference $D_i$, and $10^{100}$ terms.
For a sequence of non-negative integers $X = (X_1, X_2, \dots, X_N)$ of length $N$ with sum $M$, the score $f(X)$ of $X$ is defined as follows.
- $\displaystyle f(X) = \sum_{i = 1}^{N}$ (the sum of the first $X_i$ terms of the $i$-th arithmetic sequence)
Here, the sum of the first $0$ terms is defined to be $0$.
When you can freely choose a sequence of non-negative integers $X$ of length $N$ with sum $M$, find the maximum possible value of $f(X)$.
Constraints
- All input values are integers.
- $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$
Input
The input is given from standard input in the following format.
$N$ $M$ $A_1$ $D_1$ $\vdots$ $A_N$ $D_N$
Output
Output the maximum value of $f(X)$. Under the constraints of this problem, it can be shown that the absolute value of the answer is less than $2^{63}$.
Sample
Sample 1
Input
3 5 1 2 -8 5 13 -7
Output
29
There are $3$ arithmetic sequences $(1, 3, 5, \dots), (-8, -3, 2, \dots), (13, 6, -1, \dots)$.
When $X = (4, 0, 1)$, the score is $29$, and this is optimal.
Sample 2
Input
2 10 -100 -100 -10 0
Output
-100
There are $2$ arithmetic sequences $(-100, -200, -300, \dots), (-10, -10, -10, \dots)$.
When $X = (0, 10)$, the score is $-100$, and this is optimal. Note that the score can take a negative value.
Sample 3
Input
5 2000 4005698 -1849641 3217860 -4274311 9504793 -3809644 -1590549 2314 2581917 -3604118
Output
1454884836
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。