| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 32 | 9 | 9 | 42.857% |
The function $f(a_1, a_2, \ldots, a_n)$ represents the largest sum of elements on a non-empty subsegment in the array $a_1, a_2, \ldots, a_n$.
You are given an array $a_1, a_2, \ldots, a_n$.
You can spend one coin and decrease any element of $a$ by $1$.
Another function, $g(k)$, represents the smallest value of $f(a_1, a_2, \ldots, a_n)$ you can achieve by spending at most $k$ coins.
Find $g(1) + g(2) + \ldots + g(k)$. As this value may be very large, find it modulo $998\,244\,353$.
The first line of input contains one integer, $n$ ($1 \leq n \leq 100\,000$): the number of elements in $a$.
The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^8 \leq a_i \leq 10^8$).
The third line contains one integer $k$ ($1 \leq k \leq 10^{13}$).
Print $g(1) + g(2) + \ldots + g(k)$, modulo $998\,244\,353$.
5 1 -1 2 -2 3 3
5
3 -3 -5 -35 1
998244349
In the first example, $g(1)=2, g(2)=2,g(3)=1$.
In the second example, $g(1)=-4$.