No.2217 Suffix+
タグ : / 解いたユーザー数 165
作問者 :
stoq
/ テスター :
ぷら
Shirotsume
Problem Statement
There is a sequence $A = (A_1,\dots,A_N)$ of length $N$.
You may perform the following operation between $0$ and $K$ times, inclusive.
- Choose $1 \le i\le N$ and add $i$ to each of $A_i,A_{i+1}, \dots,A_N$.
Find the maximum possible value of the minimum of $A$ after the operations.
Input
$N$ $K$ $A_1$ $\dots$ $A_N$
- All input values are integers.
- $1 \le N \le 10^5$
- $0 \le K \le 10^9$
- $0 \le A_i \le 10^{14}$
Output
Output the maximum possible value of the minimum of $A$ after the operations.
Sample
Sample 1
Input
5 2 3 4 2 1 0
Output
4
For example, the following procedure is optimal.
- Choose $i = 1$ and add $1$ to $A_1,A_2,A_3,A_4,A_5$. This gives $A=(4,5,3,2,1)$.
- Choose $i = 3$ and add $3$ to $A_3,A_4,A_5$. This gives $A=(4,5,6,5,4)$.
The minimum of $A$ cannot be made greater than $4$, so the maximum value of the minimum is $4$.
Sample 2
Input
3 0 0 0 0
Output
0
Sample 3
Input
10 100 901 780 604 576 569 569 515 488 379 100
Output
724
Sample 4
Input
1 1000000000 100000000000000
Output
100001000000000
Beware of overflow.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。