No.1007 Coin Collecting
Problem Statement
$N$ points $1, 2, \dots, N$ are lined up in order on a straight line, and point $i$ has $A_i$ coins.
Ushi is initially at point $K$. Ushi can perform the following action any number of times.
- Stay at the current point or move to an adjacent point. However, Ushi cannot stay at or move to a point that has no coins left.
- Take $1$ coin from that point.
Ushi wants to end up at point $K$. Find the maximum number of coins that can be taken under this condition.
Input
$N$ $K$ $A_1$ $A_2$ ... $A_N$
Line $1$ contains the number of points $N(1 \le N \le 200\ 000)$ and Ushi's initial point $K(1 \le K \le N)$.
Line $2$ contains $N$ space-separated integers. The $i$-th integer $A_i(0 \le A_i \le 10^9)$ represents the number of coins at point $i$.
Output
Output, on $1$ line, the maximum number of coins Ushi can take.
Sample
Sample 1
Input
4 1 3 2 2 1
Output
8
All the coins at all points can be collected. For example, act in the order of points $1 \to 2 \to 3 \to 4 \to 3 \to 2 \to 1 \to 1 \to 1$.
Sample 2
Input
5 3 2 1 0 1 2
Output
0
If Ushi moves from point $3$ to another point, Ushi can never return to point $3$ in the end, so Ushi cannot move.
Sample 3
Input
5 3 3 1 3 1 3
Output
5
For example, move in the order of points $3 \to 2 \to 3 \to 4 \to 3 \to 3$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
ei1333333