o079. 4. 最佳選擇
標籤 :
通過比率 : 219人/384人 ( 57% ) [非即時]
評分方式:
Tolerant

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

內容

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

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

輸入說明

第一行輸入兩個正整數 $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 分): 無限制

輸出說明

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

範例輸入 #1
8 22
1 5 2 2 9 3 5 8
範例輸出 #1
16
範例輸入 #2
7 20
7 7 8 2 8 9 5
範例輸出 #2
0
測資資訊:
記憶體限制: 256 MB
提示 :

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

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

標籤:
出處:
2024年6月APCS [管理者: algo.seacow@ ... (演算法海牛) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
40906 APCS_Guide (APCS Guide) o079
1621 2024-06-17 14:43
40913 a0916933001@ ... (小律) o079
APCS 20240616 題解
817 2024-06-17 17:08
40919 sophie198205 ... (闕河正) o079
601 2024-06-17 22:43
42018 justin.sw.ya ... (pacfrog) o079
一個思路
204 2024-09-20 20:15
41634 jone921216@g ... (鍾帛勳) o079
220 2024-08-12 16:04