APCS 2024.06實作題題解 –- C++與Python

在這份筆記中，我們說明APCS 2024年6月實作題考試的題目解說。這些題目是根據ZeroJudge上的版本，與真實考試的版本題意應該是一樣的，但題目敘述、測資與環境並不一定相同。

每一題的題解都包含題意分析、演算法、C/C++範例程式與Python範例程式。其中後兩個單元是獨立的，也就是必要的說明會在兩個單元重複出現，為了方便有些人只看其中一種語言。

第一題 特技表演 (ZeroJudge o076)

題意分析

(題目連結)1.特技表演
在一個正整數序列

$h$中，要找出最長連續遞減的區段，輸出其長度。

演算法構思與程式流程

我們由左往右歷遍全部的點，記錄著目前的下降區段的長度，當新的點進來時：

• 如果新的點比前一點小：目前的下降區段可以多延伸至新的點；
• 否則，目前的下降區段便中斷了，新的點成為下一個下降區段的起點。

為了記錄最長的下降區段長度，我們另外用一個變數維護好目前所看到的最長區段長度。

C/C++範例程式

我們不需要紀錄整個序列，因此以prev紀錄前一個高度，curr為目前看到的高度，ilen則是目前區段的長度。prev的初值給予不可能的小的-1，這樣寫比較方便。接著跑一個

$n$次的迴圈，每次讀取一個高度curr，然後根據前述流程更新ilen。
在每一回合結束時，更新prev以及比對ilen是否比最長的區段更長，若是，更新之。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, i,ilen=0,prev=-1,curr=0,imax=0;
    scanf("%d",&n);
    for (i=0;i<n;i++) {
        scanf("%d",&curr);
        if (curr > prev) { // restart a new run
            ilen = 1;
        } else {
            ilen++; // current length+1
        }
        prev = curr;
        if (ilen > imax) imax = ilen;
    }
    printf("%d\n",imax);
    return 0;
}

Python範例程式

使用Python者需要對list有基本認識以方便處理輸入，本題一開始我們將所有輸入先讀入到一個list

$h$。

以imax紀錄目前最長的區段，以ilen紀錄目前區段的長度，兩者的初值給予1代表目前

$h[0]$這個區段的起點。
迴圈從1開始，第6行如果是高度下降，延伸目前的區段；否則，當作新區段的起點。第10行是嘗試更新最長區段的長度。

n = int(input())
h = [int(x) for x in input().split()]
imax = 1 # max length
ilen = 1 # current length
for i in range(1,n): # iterate the heights
    if h[i] <= h[i-1]: # extend the current length
        ilen += 1
    else:
        ilen = 1 # start a new decreasing segment
    imax = max(imax,ilen) # update the best answer
#
print(imax)

這一題資料量很小，也可以用效率較差但更直覺的方法做。嘗試以每一個點

$i$當做區段的起點，計算下降區段的長度。

n = int(input())
h = [int(x) for x in input().split()]
imax = 0 # max length
for i in range(n): # try start at i
    j = i+1
    while j<n and h[j]<=h[j-1]:
        j += 1
    # decreasing = i ~ j-1
    imax = max(imax,j-i) # update the best answer
#
print(imax)

第二題 電子畫布 (ZeroJudge o077)

題意分析

(題目連結) 2.電子畫布
模擬在一個

$h\times w$的格子點塗色，每次點在

$(r,c)$的位置，將距離

$(r,c)$不超過

$t$的每一個格子點都加上

$x$。其中距離的計算方式是列差值加上行差值，這種距離計算方式也稱為曼哈頓距離或L1距離。

演算法構思與程式流程

這就是個模擬的題目，且相對簡單。我們以矩陣的橫列與直行來定義位置，

$(r,c)$代表第

$r$個橫列的第

$c$個直行的位置，列與行的編號皆從0開始。每一次的塗色，我們可以歷遍所有格子，檢查距離，若距離符合就將該格子加上

$x$。我們可以稍稍聰明一點，不需要檢查所有格子，只要從第

$r-t$列到

$r+t$列，從第

$c-t$行到

$c+t$行，因為當列差值或行差值超過

$t$時，距離必然大於

$t$。

C/C++範例程式

這個簡單的題目，C與C++差異不大，以下提供C的寫法。

#include <stdio.h>
#include <stdlib.h>
int main() {
    int h,w,n, i, r,c,t,j,x,k;
    int grid[25][25]={0};
    scanf("%d%d%d",&h,&w,&n);
    for (k=0;k<n;k++) {
        scanf("%d%d%d%d",&r,&c,&t,&x);
        for (i=r-t; i<=r+t; i++) {
            for (j=c-t; j<=c+t; j++) {
                if (i>=0 && i<h && j>=0 && j<w && abs(i-r)+abs(j-c)<=t)
                    grid[i][j] += x;
            }
        }
    }
    for (i=0; i<h; i++) {
        for (j=0; j<w-1;j++) printf("%d ",grid[i][j]);
        printf("%d\n",grid[i][w-1]);
    }
    return 0;
}

Python範例程式

第1行讀入

$h,w,n$，第2行初始一個

$h$列

$w$行的二維矩陣，初值均為0。以下做

$n$次，每次處理一個著色。
第4行輸入一次著色的參數

$r,c,t,x$。檢查第

$p$列第

$q$行，如果沒有出界且距離滿足條件，就將該格子加上

$x$。
最後是輸出，逐行將矩陣內容印出，印出一列可以簡單用第11行的指令即可。

h,w,n = [int(x) for x in input().split()]
grid = [[0]*w for i in range(h)]
for i in range(n):
    r,c,t,x = [int(x) for x in input().split()]
    for p in range(r-t,r+t+1):
        for q in range(c-t,c+t+1):
            if 0<=p<h and 0<=q<w and abs(p-r)+abs(q-c)<=t:
                grid[p][q] += x
#
for row in grid:
    print(*row)

第三題 缺字問題 (ZeroJudge o078)

題意分析

(題目連結) 3. 缺字問題
本題大意是先給你一個字母的集合

$alpha$代表可以使用的字元，接著給一個字串

$S$，以及一個正整數

$l$，請找出長度

$l$且不出現在

$S$中的字典序最小字串。
例如，若給定的字母集為{ a, c, m } 且

$S$ = accaamcm，若指定長度

$l$ = 2，長度為2的字串共有9個，其字典順序為aa < ac < am < ca < cc < cm < ma < mc < mm，可以看出字典序最小沒出現在S中的是ma。

演算法構思與程式流程

使用很直覺的想法，既然要找出字典序最小的字串，我們就依照字典序一一產生所有長度

$L$且字母在給定集合中的字串，對於每一個產生出來的字串，我們去比對他是否出現在

$S$中，第一個找到沒出現在

$S$中的就是答案。

要實現以上想法有很多個做法，需要的技巧有兩個：

1. 如何依照字典序產生長度
   $L$的字串
2. 如何比對一個字串是否在
   $S$中。

假設

$K$是字母集的大小，而

$n$是

$S$的長度。
先看第二點，C++與Python都有內建功能可以在一個字串中找尋另外一個字串，但是在本題中不適用，因為長度

$L$的字串有

$K^L$個，即使

$L$很小可以視為常數，直接使用字串比對來檢查也需要花

$O(n\times K^L)$的時間。本題參數範圍此法只能通過第一子題。

因為要做多次的搜尋，將搜尋對象做預先處理來加快速度是應該有的思維。常用的方法是排序後二分搜，或者以字典(hash table)儲存後搜尋。這兩個方法在本題中應該都可以，不過以下我們介紹一種更加簡單且有效率的方法。

給定字母集以及長度之後，所有的字串可以依照字典序對應到0 ~

$K^L-1$整數，這相當於一個

$K$進制的數字系統是一樣的，只是長度把它限制在

$L$。我們常用的10進制數字系統也就是字母集是0 ~ 9的情形。

所以我們可以將

$S$中長度為

$L$的字串所對應到的整數全部用一個大小為

$K^L$的表格

$chk$來儲存，

$chk[i]$=True表示對應到整數

$i$的字串有出現在

$S$中。
更方便的是，我們不需要產生所有字典序的字串，只要由0開始歷遍整數找到第一個不出現的

$i$就可以了，找到之後，把第

$i$個字串解碼回去就可以了，此解碼的程序就像是10進制轉換2進制的做法。

這個方法的時間複雜度是

$O(K^L+n)$，在編碼時我們可以用一點小技巧，讓每一個長度

$L$的字串可以在

$O(1)$時間完成編碼，詳細作法在下一節中說明。

C/C++範例程式

由於C與C++對字串的處理有較大的差異，我們展示兩種寫法。
先展示C++的寫法。

第6行的chk是用來檢查的表格，這裡用bool，第7行的irank是將給定字母集的字母對應到0 ~

$K-1$，這裡大小直接開128，用字母的ASCII來對應。第14行的變數kl是用來存

$k^l$。

// encode to int
#include <bits/stdc++.h>
using namespace std;
#define N 500010
#define KL 600000
bool chk[KL]={false};
int irank[128]; // rank of char in alphabet

int main() {
    string s, alpha;
    int leng,i,j;
    cin >> alpha >> leng >>s;
    int n=s.length(), k = alpha.length(),kl=1,p=0;
    for (i=0;i<leng;i++) kl *=k; // k^l
    for (i=0;i<k;i++) irank[alpha[i]] = i; // rank of each alphabet
    // encode all substring of leng
    for (p=0,i=0; i<leng;i++) p = p*k+irank[s[i]]; // first substring
    chk[p] = true;
    for (i=leng; i<n; i++) { // substring ended at i
        p = (p*k+irank[s[i]])%kl; // rolling encoding
        chk[p] = true;
    }
    string ans(leng,'0');
    for (i=0; i<kl && chk[i]; i++) ; // i = first missing code
    // decode ans
    j = leng-1;
    while (i) {
        ans[j--] = alpha[i%k];
        i /= k;
    }
    while (j>=0) ans[j--] = alpha[0]; // leading 0
    cout << ans <<'\n';
    return 0;
}

第17 ~ 22行是將

$s$中長度

$leng$的所有字串進行編碼轉換為整數存入chk中，這裡用了一點技巧，第17行先編第一個s[0] ~ s[leng-1]字串，對於之後的每一個，我們不重算，而將前一個乘上

$k$等於左移一位，加上下一個，再%kl去除最左邊的。
第24行用一個for迴圈找到第一個沒出現的

$i$，然後開始解碼，解碼的程序就是每次用 i%k 找出最後一位，然後 /=k 右移一位，這個程序跟二進位轉換是一樣的。稍微要注意如果位數不足前面要補alpha[0]，所以我們ans的初值給予全部alpha[0]。

下面是C的寫法，字串是字元陣列，這個部分與C++比較不同，其他大同小異。

// encode to int and dfs generate each
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 500010
#define KL 600000
char s[N],chk[KL]={0};
int rank[128]; // rank of char in alphabet

int main() {
    char alpha[20];
    int leng,i,j;
    scanf("%s%d%s",alpha,&leng,s);
    int n=strlen(s), k=strlen(alpha),kl=1,p=0;
    for (i=0;i<leng;i++) kl *=k; // k^l
    for (i=0;i<k;i++) rank[alpha[i]] = i; // rank of each alphabet
    // encode all substring of leng
    for (p=0,i=0; i<leng;i++) p = p*k+rank[s[i]]; // first substring
    chk[p] = 1;
    for (i=leng; i<n; i++) { // substring ended at i
        p = (p*k+rank[s[i]])%kl; // rolling encoding
        chk[p] = 1;
    }
    char ans[20];
    for (i=0; i<kl && chk[i]; i++) ; // i = first missing code
    // decode ans
    j = leng-1;
    while (i) {
        ans[j--] = alpha[i%k];
        i /= k;
    }
    while (j>=0) ans[j--] = alpha[0]; // leading 0
    ans[leng] = '\0';
    printf("%s\n",ans);
    return 0;
}

Python範例程式

以下介紹Python的範例。

第6行的變數kl是用來存

$k^l$，這裡用pow函數直接算。第7行的rank是將給定字母集的字母對應到0 ~

$k-1$，這裡用了dict來寫比較方便。第8行的chk是用來檢查的表格，這裡用bool。
第9 ~ 14行是將

$s$中長度

$l$的所有字串進行編碼轉換為整數存入chk中，這裡用了一點技巧，第10行先編第一個s[0:l]字串，以後每一個我們不重算，我們將前一個乘上

$k$等於左移一位，加上下一個，再%kl去除最左邊的一位。
第15行用找到第一個沒出現的 i，本題保證一定存在，所以可以直接用index找出串列中的第一個。然後開始解碼，解碼的程序就是每次用i%k找出最後一位，然後//=k右移一位，這跟二進位轉換是一樣的程序。稍微要注意如果位數不足前面要補alpha[0]，所以我們ans的初值給予全部alpha[0]。
此處留意Python的字串是不可修改的物件，我們先做list of string，然後用join把他們串接在一起。

# encode to int
alpha = input()
l = int(input())
s = input()
n,k = len(s),len(alpha)
kl = pow(k,l)
rank = {c:i for i,c in enumerate(alpha)} 
chk = [False]*kl
code = 0 # encode s[:l]
for i in range(l): code = code*k+rank[s[i]]
chk[code] = True
for c in s[l:]: #rolling encoding 
    code = (code*k+rank[c])%kl
    chk[code] = True
i = chk.index(False) # find the first missing i
# decode i   
ans = [alpha[0]]*l # initial all alpha[0]
for j in range(l-1,-1,-1):
    ans[j] = alpha[i%k]
    i //= k
ans = "".join(ans)
print(ans)

由於Python的set/dict (hash table)是個很容易使用的東西，我們再給另外一種使用set的寫法。
第7行一行就把

$s$中所有的長度為

$l$的子字串存入d。第6行是用來記每一個字母他的下一個是誰。第8行是第一個字串，然後用while依序產生下一個，第10行是hash table的搜尋，執行速度是很快的。第13行開始找下一個字串的程序類似於10進制系統中的做法，例如581的下一個是582，19的下一個是20，而1999的下一個是2000。具體的程序是這樣的：由後往前找到不是字母集中最後一個字母alpha[-1]的位置，也就是還可以加一的最低位置，其中加一是指設為字母集中的下個字母。將此字母加一，然後把他後面的每一個位置設為最小的alpha[0]。第16行這裡的加一就是用前面建好的succ。

alpha = input()
l = int(input())
s = input()
n = len(s)
k = len(alpha)
succ = {p:q for p,q in zip(alpha, alpha[1:])}
d = set(s[i:i+l] for i in range(n-l+1))
ans = alpha[0]*l
while True: #always found
    if ans not in d:
        break
    # next
    i = l-1
    while ans[i]==alpha[-1]: # always found
        i -= 1
    ans = ans[:i]+succ[ans[i]]+alpha[0]*(l-i-1)
    #print(ans)
#
print(ans)
            

第四題 最佳選擇 (ZeroJudge o079)

題意分析

(題目連結) 4.最佳選擇
有

$n$ 個正整數排成一列，依序是

$a(1),a(2),\dots a(n)$。我們要挑選總和最大的prefix與suffix，但必須滿足：

1. 兩段不重疊
2. 總和不超過lim
3. 偶數與奇數的個數相等。

所謂prefix(前綴)是指序列前方的連續一段，而suffix則是後面連續的一段。

演算法構思與程式流程

有幾個條件限制，讓題目看起來比較混亂。其實找頭尾個一段與找中間一段是一樣的，因為兩者是互補的，找頭尾一段總和不超過lim就等價於找中間一段不小於

$totalSum-lim$。這裡我們可以假設

$lim\le totalSum$，否則將lim改成totalSum就好。講解本題的做法前，先看一下基本型的做法。

基本sliding window

這類型題目的基本型是找出中間一段總和不超過lim的最大總和。

由於是正整數，單一個區間往左右延伸時，其總和必然是單調遞增的。所以很自然地可以用sliding window (或稱雙指針)的方法來做。基本觀念很簡單，我們始終關注一個區間(window)

$[le,ri]$，將區間的右端逐步往右移，每次一格，並且調整左端來維護以下的迴圈不變性：
「此區間是右端=

$ri$的條件下，總和不超過lim的最大區間。」

由於前面說到的單調性，假設前面一回合的迴圈不變性已經滿足，當右端往右移動一格時，區間的總和只會變大，它所對應到的最佳左端一定是大於等於之前的左端。我們只需要將左端往右移動到第一個讓總和不超過lim的位置即可。
演算法如下：

best = isum = 0
le = 1
for ri = 1 to n do
    isum += a[ri]
    while isum > lim do // move le 
        isum -= a[le]
        le += 1
    end while
    best = max(best,isum)
end for

由於le與ri都只有往右移動，所以時間複雜度是線性的。

本題的思考方式

與基本型相比，本題有兩個變化：

1. 要找的prefix與suffix，而非中間一段。
2. 所選取的兩段中奇數與偶數個數必須相等。

其實原理還是一樣，為了滿足奇偶個數的條件，我們對每一個prefix與suffix以它們的奇數個數減去偶數個數(以下稱為dif值)次予以分類擺放，相同dif值的前綴和放在同一個串列。對於每一個後綴，它的dif值如果是

$d$，那麼我們只能在dif值為

$-d$的前綴中尋找與他的搭配，因為這樣奇數與偶數個數才會相等。

如何在對應的串列中找到最佳搭配的前綴呢？我們的目標是前綴與後綴的和不超過某個

$lim$ 且越大越好，所以後綴和如果是

$s$，我們要找的前綴就是其和

$\le lim-s$的最大值。
當然不能用線性搜尋或枚舉比對，因為時間太慢。記得我們的前綴放入串列中都是單調遞增的，所以可以用二分搜來找。
事實上不需要，俗話說：「連續二分搜不如一路爬過去」，我們由小到大產生所有的後綴和，所以要找的前綴和在每個串列中是單調下降的。每次我們只要在對應的串列中比對最後一個前綴和，如果這個前綴和太大(

$>lim-s$)，那麼它對之後的後綴也太大，我們可以直接將其刪除。

最後一個問題是如何儲存這些前綴和的串列呢？同一個串列的dif值是相同的，本題保證所有prefix的dif值的絕對值不超過

$M=2000$，所以前綴的dif值的範圍是

$-M$ ~

$M$，我們可以用

$2M+1$個串列來儲存，dif值為

$i$的放在第

$i+M$個串列。
整理一下，算法流程如下：

1. 由小到大，對於每一個prefix，計算其總和以及奇數個數減去偶數個數dif值)，依照dif值放入對應的串列；
2. 由短到長掃描所有suffix，計算其總和
   $s$與dif值
   $d$。在prefix dif值為
   $-d$的串列(就是第
   $M-d$的串列)中，由後往前刪除總和過大(
   $>lim-s$)的prefix sum。如果有滿足要求的答案(串列非空)，就嘗試更新最佳解。

注意到，每一個串列我們只在其後增加元素或刪除最後一個元素，所以其實是當做stack在使用。

C/C++範例程式

我們用vector來放串列。第13行的bal是

$2M+1$個vector來放那些串列，事實上我們是把這些串列當作堆疊在使用(看下去就知道)。
有一個容易被忽略的細節，我們必須考慮空的prefix與後綴。第15行是對應到空的prefix，其和為0，dif值也是0。接下來16 ~ 21行算每一個prefix的和與dif，將其和放入bal[M+dif]中，由於總和是單調上升，所以放入後也是遞增序列。
第22行是個細節，如果lim大於整個序列的總和，我們將其改為總和，這是要避免後面搜到的prefix與suffix重疊了。
第25 ~ 26行是找出suffix為空時的解，第27行開始逐步推suffix，對於每一個suffix，我們到第

$k=M-dif$個串列中去找，從後往前看，如果超過總和限制就把它pop掉，因為suffix的和是越來越大，所以目前已經太大的prefix未來也沒有用。第35行是更新目前看到的最佳解。
時間複雜度是

$O(n)$。

// prefix and suffix <=lim; bal[suffix] == -bal[prefix]
#include <bits/stdc++.h>
using namespace std;
#define N 300000
#define M 2000

int main() {
    int n, i,j,k,lim;
    scanf("%d%d",&n,&lim);
    vector<int> v(n);
    for (i=0;i<n;i++) scanf("%d",&v[i]);
    // partition by odd-even
    vector<int> bal[M+M+1]; // odd-even balance
    int ans = n, psum=0,dif=0,ssum=0;
    bal[M].push_back(0);
    for (i=0;i<n;i++) {
        psum += v[i];
        if (v[i]&1) dif++;
        else dif--;
        bal[M+dif].push_back(psum);
    }
    if (lim>psum) lim=psum;
    // sweep suffix
    ssum =0, dif = 0;
    while (bal[M].back()>lim) bal[M].pop_back();
    ans = bal[M].back(); // for empty suffix
    for (i=n-1;i>=0;i--) {
        ssum += v[i];
        if (v[i]&1) dif++;
        else dif--;
        if (abs(dif)>M) continue;
        k = M-dif;
        while (!bal[k].empty() && bal[k].back()+ssum > lim)
            bal[k].pop_back();
        if (!bal[k].empty()) ans=max(ans,ssum+bal[k].back());
    }
    printf("%d\n",ans);
    //fprintf(stderr,"lim,ans=(%d,%d), max dif=%d, min dif=%d\n",lim,ans,dmax,dmin);
    return 0;
}

這個題目用C來寫的時候會遇到一點小麻煩，在前面C++的實作中，我們用vector來存那些串列(堆疊)，但C沒有可變長度的陣列，如果宣告

$4001$個長度

$300000$的陣列，記憶體空間可能太大。因為這些串列都是不相交的，解決的方法是把所有的prefix sum 還是放在一個陣列中，用一個next陣列指到每一個串列中的下一個位置。以下是範例程式，我們就不多解釋，僅供有興趣的人參考。

// prefix and suffix <=lim; bal[suffix] == -bal[prefix], c version
#include <stdio.h>
#define N 300010
#define M 2000
int v[N],psum[N],next[N],top[M+M+1];

int main() {
    int n, i,j,k,lim;
    scanf("%d%d",&n,&lim);
    for (i=1;i<=n;i++) scanf("%d",&v[i]); // 1-index
    for (i=0;i<M+M+1;i++) top[i]=-1;
    int ans = 0, dif=0;
    // partition by odd-even
    psum[0] = 0;
    next[0] = -1;
    top[M] = 0; // push 0 (empty prefix)
    for (i=1; i<=n; i++) {
        if (v[i]&1) dif++;
        else dif--;
        psum[i] = psum[i-1]+v[i]; // prefix sum
        if (dif>M || dif<-M) fprintf(stderr,"bound exceed\n");
        next[i] = top[M+dif]; // push i into stack (M+dif)
        top[M+dif] = i;
    }
    if (psum[n]<lim) lim=psum[n];
    // sweep suffix
    int ssum =0;
    while (psum[top[M]] > lim) top[M] = next[top[M]];
    ans = psum[top[M]]; // for empty suffix
    dif = 0;
    for (i=n; i>0; i--) {
        ssum += v[i];
        if (v[i]&1) dif++;
        else dif--;
        if (dif>M || dif<-M) continue;
        k = M-dif; //
        while (top[k]!=-1 && psum[top[k]]+ssum > lim)
            top[k] = next[top[k]];
        if (top[k]!=-1 && ssum+psum[top[k]]>ans)
            ans = ssum+psum[top[k]];
    }
    printf("%d\n",ans);
    return 0;
}

Python範例程式

以下是Python的寫法。第4行的stk是

$2M+1$個串列，事實上我們是把這些串列當作堆疊在使用。
有一個容易被忽略的細節，我們必須考慮空的prefix與後綴。第5行是對應到空的prefix，其和為0，dif值也是0。接下來8 ~ 13行算每一個prefix的和與dif，將其和放入stk[M+dif]中，由於總和是單調上升，所以放入後也是遞增序列。
第14行是個細節，如果lim大於整個序列的總和，我們將其改為總和，這是要避免後面搜到的prefix與suffix重疊。
第17 ~ 18行是找出suffix為空時的解，第19行開始逐步推suffix，對於每一個suffix，我們到第

$M-dif$個串列中去找，從後往前看，如果超過總和限制就把它pop掉，因為suffix的和是越來越大，所以目前已經太大的prefix未來也沒有用。第27行是更新目前看到的最佳解。
時間複雜度是

$O(n)$。

n,lim = [int(x) for x in input().split()]
v = [int(x) for x in input().split()]
M = 2000
stk = [[] for i in range(M+M+1)] # odd-even =0 at [M]
# partition prefix sum into stack
stk[M].append(0) # prefix sum=0
psum = dif = 0
for x in v:
    psum += x
    #if psum>lim: break
    if x&1: dif += 1
    else: dif -= 1
    stk[M+dif].append(psum)
if lim>psum: lim = psum
# sweep suffix
ssum = dif = 0
while stk[M] and stk[M][-1]>lim: stk[M].pop()
ans = stk[M][-1]
for x in v[::-1]:
    ssum += x
    if x&1: dif += 1
    else: dif -= 1
    if abs(dif)>M: continue
    while stk[M-dif] and stk[M-dif][-1]+ssum>lim:
        stk[M-dif].pop()
    if stk[M-dif]:
        ans = max(ans,stk[M-dif][-1]+ssum)
#
print(ans)

End