o079. 4. 最佳選擇
Tags :
Accepted rate : 129人/263人 ( 49% ) [非即時]
評分方式:
Tolerant

最近更新 : 2024-06-17 09:40

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
16
Sample Input #2
7 20
7 7 8 2 8 9 5
Sample Output #2
0
測資資訊:
記憶體限制: 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 [管理者: algo.seacow@ ... (演算法海牛) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
40913 a0916933001@ ... (小律) o079
APCS 20240616 題解
435 2024-06-17 17:08
40906 APCS_Guide (APCS Guide) o079
889 2024-06-17 14:43
41228 xsw20080329@ ... (敢不敢讓我過) o079
c
17 2024-07-12 20:20
40919 sophie198205 ... (闕河正) o079
251 2024-06-17 22:43
40889 niceyuehen@g ... (餘切) o079
C++ 題解
949 2024-06-17 00:51