owned this note
owned this note
Published
Linked with GitHub
# APCS 2024.06實作題題解 --- C++與Python
在這份筆記中，我們說明APCS 2024年6月實作題考試的題目解說。這些題目是根據ZeroJudge上的版本，與真實考試的版本題意應該是一樣的，但題目敘述、測資與環境並不一定相同。
每一題的題解都包含題意分析、演算法、C/C++範例程式與Python範例程式。其中後兩個單元是獨立的，也就是必要的說明會在兩個單元重複出現，為了方便有些人只看其中一種語言。
## 第一題 特技表演 (ZeroJudge o076)
### 題意分析
[(題目連結)1.特技表演](https://zerojudge.tw/ShowProblem?problemid=o076)
在一個正整數序列$h$中，要找出最長連續遞減的區段，輸出其長度。
### 演算法構思與程式流程
我們由左往右歷遍全部的點，記錄著目前的下降區段的長度，當新的點進來時：
* 如果新的點比前一點小：目前的下降區段可以多延伸至新的點；
* 否則，目前的下降區段便中斷了，新的點成為下一個下降區段的起點。
為了記錄最長的下降區段長度，我們另外用一個變數維護好目前所看到的最長區段長度。
### C/C++範例程式
我們不需要紀錄整個序列，因此以prev紀錄前一個高度，curr為目前看到的高度，ilen則是目前區段的長度。prev的初值給予不可能的小的-1，這樣寫比較方便。接著跑一個$n$次的迴圈，每次讀取一個高度curr，然後根據前述流程更新ilen。
在每一回合結束時，更新prev以及比對ilen是否比最長的區段更長，若是，更新之。
```cpp=
#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行是嘗試更新最長區段的長度。
```python=
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$當做區段的起點，計算下降區段的長度。
```python=
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.電子畫布](https://zerojudge.tw/ShowProblem?problemid=o077)
模擬在一個$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的寫法。
```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行的指令即可。
```python=
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. 缺字問題](https://zerojudge.tw/ShowProblem?problemid=o078)
本題大意是先給你一個字母的集合$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$。
```cpp=
// 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++比較不同，其他大同小異。
```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把他們串接在一起。
```python=
# 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。
```python=
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.最佳選擇](https://zerojudge.tw/ShowProblem?problemid=o079)
有 $n$ 個正整數排成一列，依序是 $a(1),a(2),\ldots 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)$。
```cpp=
// 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陣列指到每一個串列中的下一個位置。以下是範例程式，我們就不多解釋，僅供有興趣的人參考。
```c=
// 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)$。
```python=
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**
Google Drive
Gist
Clipboard
Sign in with Wallet
