| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 72 | 44 | 41 | 59.420% |
Marko was at the Interliber book fair, and he bought $n$ books. The attraction of the $i$-th book is $k_i$. Marko arranged the books on the shelf according to their attraction values, so the first book from the left is the least attractive, and every next one to the right is more or equally attractive than the previous one.
It has been quite some time since Interliber, but Marko has only now found time to read the books. He will spend a total of $t$ minutes reading.
For each book, he can either read it in its entirety, which takes him $a$ minutes; or read only the content from the covers, which takes him $b$ minutes.
He will start from the leftmost book. After finishing the current book (either entirely or just the content from the covers), he moves on to the next book, which is the first one to the right of the book he just read. Marko’s inspiration is equal to the sum of the attraction values of the books he has read in their entirety. What is the maximum value of Marko’s inspiration after $t$ minutes?
Note: If Marko starts reading a book but fails to finish it before the end of $t$ minutes, that book does not contribute to his inspiration.
The first line contains integers $n,ドル $t,ドル $a$ and $b$ (1ドル ≤ n ≤ 2 \cdot 10^5,ドル 1ドル ≤ t ≤ 10^9,ドル 1ドル ≤ b < a ≤ 10^9$), the number of books, the time Marko will spend reading, time required for reading a book and the time required to read the content from the covers.
The second line contains $n$ integers $k_i$ (1ドル ≤ k_i ≤ 10^9,ドル $k_i ≤ k_{i+1}$), the attraction values of books.
In the first and only line print Mirko’s maximal inspiration after $t$ minutes.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 7 | $k_i = k_{i+1}$ for each $i = 1, \dots , n - 1$ |
| 2 | 27 | $n ≤ 1,円 000$ |
| 3 | 36 | No additional constraints. |
3 5 2 1 2 2 4
6
For example, Marko can read the first book in its entirety, read only the content from the covers of the second book, and read the third book in its entirety, thus achieving the maximum possible inspiration.
2 10 3 1 3 3
6
4 10 3 2 3 4 5 6
12