c078. 4. 最佳選擇

Content

給一個長度為 $n$ 的正整數序列 $a_1, a_2, \dots, a_n$，你可以執行多次操作 (包含 0 次)，每次操作只能選擇這個序列的第一個或最後一個數字，再將這個數字從序列中刪除並自己搜集起來。

求滿足總和不超過 $k$ 且搜集的數字奇數和偶數個數相同的條件下，所能搜集的數字總和最大為多少。

Input

第一行輸入兩個正整數 $n, k$ $(1 \le n \le 3 \times 10^5, 1 \le k \le 10^9)$。

第二行有 $n$ 個正整數 $a_1, a_2, \dots, a_n (1 \le a_i \le 5 \times 10^3)$。

保證 $\forall i \in [1, n]$，前 $i$ 個數字的奇數和偶數數量差距不超過 $2 \times 10^3$。

(20 分): $n = 10^3$
(80 分): 無限制

Output

輸出滿足題目需求的最大值。

Sample Input #1

8 22
1 5 2 2 9 3 5 8

Sample Output #1

Sample Input #2

7 20
7 7 8 2 8 9 5

Sample Output #2

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (5%): 1.0s , <1K
公開測資點#1 (5%): 1.0s , <1M
公開測資點#2 (5%): 1.0s , <1M
公開測資點#3 (5%): 1.0s , <1M
公開測資點#4 (5%): 1.0s , <10M
公開測資點#5 (5%): 1.0s , <10M
公開測資點#6 (5%): 1.0s , <10M
公開測資點#7 (5%): 1.0s , <10M
公開測資點#8 (5%): 1.0s , <10M
公開測資點#9 (5%): 1.0s , <10M
公開測資點#10 (5%): 1.0s , <10M
公開測資點#11 (5%): 1.0s , <10M
公開測資點#12 (5%): 1.0s , <10M
公開測資點#13 (5%): 1.0s , <10M
公開測資點#14 (5%): 1.0s , <10M
公開測資點#15 (5%): 1.0s , <10M
公開測資點#16 (5%): 1.0s , <10M
公開測資點#17 (5%): 1.0s , <10M
公開測資點#18 (5%): 1.0s , <10M
公開測資點#19 (5%): 1.0s , <10M

Hint ：

範測 1:
1 5 2 2 9 3 5 8
選擇紅色數字，總和為 $16$

範測 2:
沒有任何符合題目條件的選法，總和為 $0$

Tags:

出處:

2024年6月 APCS 演算法海牛 [管理者： ktlai (K．我已霸榜．Tlai) ]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」