---
# System prepended metadata

title: 2024/6/29 APCS 第六場模擬賽 題解
tags: [題解]

---

# 2024/6/29 APCS 第六場模擬賽 題解

## 大智慧學苑-畢業旅行囉 (Trip)
> 出題者：Howard
> 難度：p1
> 考點：模擬
### Statement
已經到了六月，大智慧學苑正準備著學員們的畢業旅行，大智慧學苑院長 Chung 非常奇怪，和大部分學校不同的是他想要在畢業典禮後再舉辦畢業旅行，院長這次破例，想要幫所有學員出飛機票錢，但是他們要搭乘的航空公司有很多優惠，此優惠根據不同年齡層會有更動，給定 $n$ 個人，還有優惠的年齡區間 $L_i、R_i$ 優惠價，以及原價，請你寫程式告訴院長需要花多少錢。
若年齡未在所有優惠年齡區間，則以原價計算。
年齡層不可能會有重複。
### Input
第一行有兩個數字 $n,m\ (1\leq n\leq 1000,\ 10\leq m\leq 1000)$ 代表有 $n$ 位學員以及機票原價為 $m$
第二行有 $n$ 個數字 $a_1, a_2, a_3,...,a_n\ (1\leq a_i\leq 100)$ 代表每個人的年齡
第三行有一個數字 $k (1\leq k\leq 50)$ 代表有幾筆優惠
第四行開始總共有 $k$ 行，每行有三個數字 $L_i, R_i, P_i\ (1\leq L_i\leq R_i\leq 100,\ 1\leq P_i < m)$ 代表年齡從 $L_i$ (包含) 到 $R_i$ (包含) 的優惠價格為 $P_i$
### Output
輸出共一個數字代表院長需要付的所有機票錢。
### Testcase
- Input 1
```
5 100
7 10 5 20 15
3
5 10 50
1 3 10
20 30 60
```
- Output 1
```
310
```
### Subtask
- Subtask 1 (50%) - $k=1$
- Subtask 2 (50%) - 無其他限制
### Solution
- Subtask 1：由於只有一組 $L, R$ ，所以只要在全部輸入後再跑一次迴圈看看有哪些是符合優惠方案的，是的話就是用優惠方案的價錢，不是的話就用原機票價錢 $k$ 計算。
- Subtask 2：針對每個人都去試試看是否符合優惠方案的年齡區間，由於題目保證年齡區間不會重複，所以只要找到一個符合的區間就一定是那個答案。
### Code
- Subtask 1
```cpp=
#include<bits/stdc++.h>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    int a[n];
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int k;
    cin >> k;
    int L, R, P;
    cin >> L >> R >> P;
    int ans = 0;
    for(int i = 0; i < n; i++) {
        if(a[i] >= L && a[i] <= R) ans += P;
        else ans += m;
    }
    cout << ans << '\n';
    return 0;
}
```
- Subtask 2
```cpp=
#include<bits/stdc++.h>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    int a[n];
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int k;
    cin >> k;
    int L[k], R[k], P[k];
    for(int i = 0; i < k; i++) {
        cin >> L[i] >> R[i] >> P[i];
    }
    int ans = 0;
    for(int i = 0; i < n; i++) {
        bool used = 0;
        for(int j = 0; j < k; j++) {
            if(a[i] >= L[j] && a[i] <= R[j]) {
                used = 1;
                ans += P[j];
                break;
            }
        }
        if(!used) ans += m;
    }
    cout << ans << '\n';
    return 0;
}
```
- Python by 橘子
```python=
n,m = map(int,input().split())
a = list(map(int,input().split()))
b = [m]*n
for _ in range(int(input())):
    l,r,p = map(int,input().split())
    for i in range(n):
        if l<=a[i]<=r:
            b[i] = min(b[i],p)
print(sum(b))
```

## 烤肉吧！ (barbecue)

> 出題者：Cheng
> 難度：p2
> 考點：二維陣列操作
### Statement

<center>
    <img src="https://hackmd.io/_uploads/rJ9I9V6UC.png">
</center>


香噴噴又油亮亮的烤肉是 Cheng 的最愛呢！
在美好的夜晚當中，明亮的火光在你眼前，香氣撲鼻而來，好想大喊一句「バーベキューは最高！」
今天又在烤肉的 Cheng 想要烤出超美味的烤肉，於是依照路邊撿到的黑暗聖典來烤出美味的烤肉！

<center>
    <img src="https://hackmd.io/_uploads/SJs5cNpLC.png">
</center>

<br>

我們可以把烤肉網和烤爐皆視為一個大小相同的 $n \times m$ 矩陣，烤爐一開始在第 $i$ 列第 $j$ 行會有 $H_{i,j}$ 的焰度，每分鐘結束時焰度會增加 $y_{i,j}$，(注意到 $y_{i,j}$ 可能是負的，所以烤爐的焰度可能會越來越低，但若低於 $0$ 皆須視為 $0$)。

Cheng 在烤肉網上放上了 $n \times m$ 塊肉，每塊大小恰等於烤肉網上的每一格，我們可以簡單的將肉劃分為正反兩面，肉正反兩面每格的熟度以及溫度初始為 $0$，每分鐘每個格子上的肉的溫度會加上火爐該格當時的焰度，格子上的肉正(反)面每吸收 $k$ 度，該格子上的肉正(反)面熟度就會增加 $1$。若每塊肉正反兩面的熟度都大於或等於 $R$，就代表所有肉都熟了！Cheng 就會把它們拿下來享用！

黑暗聖典的指示有兩種，每分鐘聖典都會有下列其中一種指示：
* $S$：把每塊肉翻面
* $.$：放著繼續烤

黑暗聖典上面說，只要時間一到就要馬上做該時間要做的操作，且因為 Cheng 的手腳很快，所以每分鐘 Cheng 會先操作完，肉再吸收烤爐焰度，也就是說每分鐘會依序執行：聖典操作 -> 烤爐加熱烤肉 -> 烤肉熟度改變 -> 烤爐更新焰度。

另外，烤肉把肉烤焦也是一件很正常的事，若肉的正(反)面熟度嚴格大於 $R \times 2$，則這塊肉的正(反)面會燒焦 (燒焦只是過熟，所以依然算熟)，為了驗證黑暗聖典的有用程度，Cheng 想要額外知道正面和反面總共有幾個格子上的肉燒焦 (正反面都要算一次，假如有 $3$ 個正面焦掉、有 $2$ 個反面焦掉，則總計為 $5$)。

Cheng 想知道在 $t$ 分鐘過後依照黑暗聖典的指示所有肉會不會熟，以及正面和反面總共有幾個格子上的肉燒焦了？(需要注意如果烤到一半就全熟了，則會直接被拿起來，不用等到 $t$ 分鐘結束)

大家一起開心的吃烤肉吧！
### Input
輸入第一行將有兩個整數 $n, m\ (1 \le n, m \le 10)$。

輸入第二行將有三個整數 $t\ (1 \le t \le 1000), k, R\ (1 \le k, R \le 500)$。

輸入第三行將有一個字串 $S\ (|S| = t,\ S$ 只會有 "S" 或 "." 兩種字元$)$ 代表黑暗聖典上說的操作 (字串第 $1$ 個字元代表第 $1$ 分鐘要做的操作)。

接著有 $n$ 行，每行會有 $m$ 個數字 $H_{i,j}\ (0 \le H_{i,j} \le 100)$，代表烤爐第 $i$ 列、第 $j$ 行初始的焰度。

輸入第一行將有兩個整數 $n, m\ (1 \le n, m \le 10)$。

輸入第二行將有三個整數 $t\ (1 \le t \le 1000), k, R\ (1 \le k, R \le 500)$。

輸入第三行將有一個字串 $S\ (|S| = t,\ S$ 只會有 "S" 或 "." 兩種字元$)$ 代表黑暗聖典上說的操作 (字串第 $1$ 個字元代表第 $1$ 分鐘要做的操作)。

接著有 $n$ 行，每行會有 $m$ 個數字 $H_{i,j}\ (0 \le H_{i,j} \le 100)$，代表烤爐第 $i$ 列、第 $j$ 行初始的焰度。

最後有 $n$ 行，每行會有 $m$ 個數字 $y_{i,j}\ (-10 \le y_{i,j} \le 10)$，代表第 $i$ 列、第 $j$ 行烤爐每分鐘會增加的焰度，請注意，烤爐焰度最低為 $0$，不會是負的。

### Output
輸出兩個數字，依序代表 $t$ 分鐘後所有烤肉有沒有都熟了 (輸出 $0$ 代表仍有肉沒熟、$1$ 代表所有肉正反每格都熟了)、正面和反面總共有幾個格子上的肉燒焦。(需要注意如果烤到一半就全熟了，則會直接被拿起來，不用等到 $t$ 分鐘結束)

### Testcase
- Input 1
```
2 2
3 5 5
...
70 35
80 2
8 10
8 6
```
- Output 1
```
0 3
```
- Input 1
```
2 2
3 5 5
.S.
5 80
12 17
6 5
0 -3
```
- Output 1
```
0 2
```
### Subtask
- Subtask 1 (50%) - $S$ 只由 "." 組成
- Subtask 2 (50%) - 無其他限制

### Note
每秒依序執行：聖典操作 -> 烤爐加熱烤肉 -> 烤肉熟度改變 -> 烤爐更新焰度

### Solution
可以發現這是個二維陣列操作的題目
我們要找到 $(i,j)$ 格到底累積了多少次 $k$ 溫度
我們可以將 $(i,j)$ 的溫度差除以 $k$ 來得知該時間點會増加多少熟度
(加上後整個會累積多少 $k$) $-$ (加上前累積了多少 $k$)
在每個時間點操作後都去檢查該塊肉是否熟了，熟了就直接拿下來計算燒焦區域有多少
其實 sub1 跟 sub2 的差別只是「記得將上層與下層的溫度做 swap 的動作 (翻面)」
### Code
- Subtask 1
```cpp=
void sol()
{
	int n, m;
	cin >> n >> m;
	int t, k, R;
	cin >> t >> k >> R;
	vector<vector<vector<int>>> h(2, vector<vector<int>>(n, vector<int>(m, 0))), T(2, vector<vector<int>>(n, vector<int>(m, 0)));
	int down = 0, top = 1;
	vector<vector<int>> H(n, vector<int>(m)), y(n, vector<int>(m));
	string s;
	cin >> s;
	for(auto &v : H) for(int &it : v) cin >> it;
	for(auto &v : y) for(int &it : v) cin >> it;
	int jiao = 0;
	for(int time = 0; time < t; time++){
		for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){
			int dis = (h[down][i][j] + H[i][j])/k - h[down][i][j]/k;
			h[down][i][j]+=H[i][j];
			if(H[i][j] && dis) T[down][i][j]+=dis;
			H[i][j]+=y[i][j], H[i][j] = max(0, H[i][j]);
		}
		bool check = 1;
		for(int dir = 0; dir < 2; dir++) for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){
			if(T[dir][i][j] < R) check = 0;
		}
		if(check){
			for(int dir = 0; dir < 2; dir++) for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){
				if(T[dir][i][j] > 2*R) jiao++; 
			}
			cout << 1 << ' ' << jiao << '\n';
			return;
		}
	}
	for(int dir = 0; dir < 2; dir++) for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){
		if(T[dir][i][j] > 2*R) jiao++; 
	}
	cout << 0 << ' ' << jiao << '\n';
}
```
- Subtask 2
```cpp=
void sol()
{
	int n, m;
	cin >> n >> m;
	int t, k, R;
	cin >> t >> k >> R;
	vector<vector<vector<int>>> h(2, vector<vector<int>>(n, vector<int>(m, 0))), T(2, vector<vector<int>>(n, vector<int>(m, 0)));
	int down = 0, top = 1;
	vector<vector<int>> H(n, vector<int>(m)), y(n, vector<int>(m));
	string s;
	cin >> s;
	for(auto &v : H) for(int &it : v) cin >> it;
	for(auto &v : y) for(int &it : v) cin >> it;
	int jiao = 0;
	for(int time = 0; time < t; time++){
		if(s[time] == 'S') swap(down, top);
		for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){
			int dis = (h[down][i][j] + H[i][j])/k - h[down][i][j]/k;
			h[down][i][j]+=H[i][j];
			if(H[i][j] && dis) T[down][i][j]+=dis;
			H[i][j]+=y[i][j], H[i][j] = max(0, H[i][j]);
		}
		bool check = 1;
		for(int dir = 0; dir < 2; dir++) for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){
			if(T[dir][i][j] < R) check = 0;
		}
		if(check){
			for(int dir = 0; dir < 2; dir++) for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){
				if(T[dir][i][j] > 2*R) jiao++; 
			}
			cout << 1 << ' ' << jiao << '\n';
			return;
		}
	}
	for(int dir = 0; dir < 2; dir++) for(int i = 0; i < n; i++) for(int j = 0; j < m; j++){
		if(T[dir][i][j] > 2*R) jiao++; 
	}
	cout << 0 << ' ' << jiao << '\n';
}
```

- Subtask 2 by Chung
```cpp=
#include<bits/stdc++.h>
using namespace std;
//declare
const int maxn = 15;
int n,m,t,k,R,cnt;
int H[maxn][maxn]; // 烤爐
int y[maxn][maxn]; // 焰度更新
int T[2][maxn][maxn]; // 兩面吸收的溫度
int M[2][maxn][maxn]; // 兩面熟度
string s;
//
int main(){
    cin>>n>>m>>t>>k>>R>>s;
    for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>H[i][j];
    for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>y[i][j];
    bool flag = 0;
    for(int x=0;x<t;x++){
        if(s[x] == 'S') flag ^= 1; // 聖典操作
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                // 烤爐加熱肉
                T[flag][i][j] += H[i][j];
                // 烤肉熟度改變
                M[flag][i][j] = T[flag][i][j] / k;
                // 烤爐更新焰度
                H[i][j] += y[i][j];
                H[i][j] = max(0, H[i][j]);
            }
        }
        // 判斷是否全熟
        bool ok = 1;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(M[0][i][j] < R) ok = 0;
                if(M[1][i][j] < R) ok = 0;
            }
        }
        // 計算焦掉的數量
        cnt = 0; // 焦掉的數量
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                cnt += (M[0][i][j] > 2*R);
                cnt += (M[1][i][j] > 2*R);
            }
        }
        if(ok){
            cout<<1<<" "<<cnt<<"\n";
            return 0;
        }
    }
    cout<<0<<" "<<cnt<<"\n";
    return 0;
}
```
- Python by 橘子
```python=
n, m = map(int,input().split())
t, k, r = map(int,input().split())
s = input()
h = [list(map(int,input().split())) for _ in range(n)]
d = [list(map(int,input().split())) for _ in range(n)]
down = [[0]*m for _ in range(n)]
up = [[0]*m for _ in range(n)]
ans1 = 0
for i in range(t):
    if s[i]=='S':
        down, up = up, down
    ed = True
    for x in range(n):
        for y in range(m):
            down[x][y] += h[x][y]
            h[x][y] = max(0,h[x][y]+d[x][y])
            if down[x][y]//k < r or up[x][y]//k < r:
                ed = False
    if ed:
        ans1 = 1
        break
ans2 = 0
for x in range(n):
    for y in range(m):
        ans2 += (down[x][y]//k>r*2)+(up[x][y]//k>r*2)
print(ans1,ans2)
```

## 蘋果樹 (Apple Tree)
> 出題者：Chung
> 難度：p3
> 考點：dfs/bfs、二分搜、前綴和
### Statement
Chung 家裡種了一棵蘋果樹，最近到了可以採收的季節，於是 Chung 決定來採收這些蘋果，為了方便，Chung 已經將樹枝用 $1 \sim n$ 進行編號 (其中樹幹編號必為 $1$)，且已經將在同個樹枝上的蘋果分類為同一組，並提供給你兩個資訊：每個樹枝連接的樹枝編號，每個樹枝上的蘋果數量。

因為 Chung 很懶惰，所以即使他有很多個籃子，卻只想要選定一個籃子來採收，但這樣就面臨了一個問題：如果採收的蘋果太少，Chung 就會覺得吃不飽，反之如果採收的蘋果太多又會造成浪費，所以他想要預先知道使用每個籃子分別可以採收多少蘋果。

Chung 會從樹幹開始採收，先採收和樹幹連接的那些樹枝們上的蘋果，再採收和那些樹枝們連接的樹枝們上的蘋果，以此類推一層一層往上採收，但是，假如採收完這一層之後就會讓籃子裝不下，那麼 Chung 就會放棄採收這一層並停止採收。

Chung 想要知道，使用每個籃子分別最高可以採收到第幾層，你能寫個程式幫幫他嗎？(樹幹為第 $0$ 層)

### Input
輸入第一行將有兩個整數 $n,m\ (1 \le n,m \le 2 \times 10^5)$，分別代表蘋果樹的樹枝數量和 Chung 擁有的籃子數量。

接著一行有 $m$ 個整數 $c_1,c_2,\dots,c_m\ (0 \le c_i \le 5 \times 10^6)$，分別代表第 $i$ 個籃子的容量 (至多可以裝的蘋果數量)。

接著會有 $n$ 行，第 $i\ (1 \le i \le n)$ 行第一個整數為 $k_i\ (1 \le k_i < n)$，代表有 $k_i$ 個樹枝和編號為 $i$ 的樹枝連接，緊接著有 $k_i$ 個整數 $x_{i,1},x_{i,2},\dots,x_{i,k_i}\ (1 \le x_{i,j} \le n,\ 1 \le j \le k_i)$，分別代表和編號 $i$ 的樹枝相連的樹枝編號，彼此之間用空白隔開。

最後一行有 $n$ 個整數 $a_1,a_2,\dots,a_n\ (0 \le a_i \le 1000)$，彼此用空白隔開，$a_i$ 代表編號為 $i$ 的樹枝上有幾顆蘋果 ($a_1$ 保證為 $0$)。
### Output
請總共輸出 $m$ 行，第 $i$ 行請輸出在使用第 $i$ 個籃子的情況下，Chung 最高可以採收到第幾層。
### Input Format
$n\ m$
$c_1\ c_2\ \dots c_m$
$k_1\ x_{1,1},x_{1,2},\dots,x_{1,k_1}$
$k_2\ x_{2,1},x_{2,2},\dots,x_{2,k_2}$
$\dots$
$k_n\ x_{n,1},x_{n,2},\dots,x_{n,k_n}$
$a_1\ a_2\ \dots a_n$
### Output Format
$ans_1$
$ans_2$
$\dots$
$ans_m$
### Testcase
- Input 1
```
6 4
0 6 8 21
2 2 3
1 1
4 1 4 5 6
1 3
1 3
1 3
0 1 6 2 7 5
```
- Output 1
```
0
0
1
2
```
### Subtask
- Subtask 1 (30%) - $n,m \le 1000$
- Subtask 2 (70%) - 無其他限制
### Solution
- Subtask 1
    - 我們可以對於每筆詢問都做一次 bfs，基於 bfs 的性質，每次走訪到的點都是層層遞增，剛好符合求深度總和的需求。
    - 題解使用到的技巧是「一次處理完同一深度的節點」，具體實作方式就是每次都一次處理完當前 queue 裡的節點，再依序將新的一層推進 queue，這樣就可以保證每次在 queue 中都是同深度的節點，這樣一來在計算同一層的總和時就會很方便。
    - 總時間複雜度：$O(nm)$
- Subtask 2
    - 觀察到每次的操作所求的資訊其實可以先被儲存起來
    - 我們只需要維護各深度蘋果總和的前綴和，就可以針對每筆詢問二分搜到總和不超過容量的最大值，$O(\log n)$ 解決
    - 題解使用 dfs 實作，並開一個陣列維護深度總和
    - 總時間複雜度：$O(n+m \log n)$
### Code
- Subtask 1
```cpp=
#include<bits/stdc++.h>
using namespace std;
//declare
const int maxn = 2e5+5;
int n,m,c[maxn],cnt[maxn];
bool vis[maxn];
vector<int> G[maxn];
//
int bfs(int cap){
    for(int i=1;i<=n;i++) vis[i] = 0;
    queue<int> q;
    q.push(1);
    vis[1] = 1;
    int sum = 0, depth = 0;
    while(q.size()){
        int sz = q.size();
        for(int i=0;i<sz;i++){
            int cur = q.front(); q.pop();
            for(int adj : G[cur]){
                if(vis[adj]) continue;
                vis[adj] = 1;
                sum += cnt[adj];
                q.push(adj);
            }
        }
        if(sum > cap) return depth;
        depth++;
    }
    return depth-1;
}
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++) cin>>c[i];
    for(int i=1;i<=n;i++){
        int k; cin>>k;
        for(int j=0;j<k;j++){
            int x; cin>>x;
            G[i].push_back(x);
        }
    }
    for(int i=1;i<=n;i++) cin>>cnt[i];
    for(int i=0;i<m;i++){
        cout<<bfs(c[i])<<"\n";
    }
    return 0;
}
```
- Subtask 2
```cpp=
#include<bits/stdc++.h>
using namespace std;
//declare
const int maxn = 2e5+5;
int n,m,c[maxn],depth[maxn],cnt[maxn],sum[maxn],max_depth;
bool vis[maxn];
vector<int> G[maxn], pre{0};
//
void dfs(int cur){
    for(int adj : G[cur]){
        if(vis[adj]) continue;
        vis[adj] = 1;
        depth[adj] = depth[cur] + 1;
        dfs(adj);
    }
    sum[depth[cur]] += cnt[cur];
    max_depth = max(max_depth, depth[cur]);
}
int main(){
    cin>>n>>m;
    for(int i=0;i<m;i++) cin>>c[i];
    for(int i=1;i<=n;i++){
        int k; cin>>k;
        for(int j=0;j<k;j++){
            int x; cin>>x;
            G[i].push_back(x);
        }
    }
    for(int i=1;i<=n;i++) cin>>cnt[i];
    vis[1] = 1;
    dfs(1);
    for(int i=1;i<=max_depth;i++) pre.push_back(pre.back() + sum[i]);
    for(int i=0;i<m;i++) cout<<upper_bound(pre.begin(),pre.end(),c[i]) - pre.begin() - 1<<"\n";
    return 0;
}
```
- Python by 橘子
```python=
import bisect
n,m = map(int,input().split())
c = list(map(int,input().split()))
con = [[int(s)-1 for s in input().split()][1:] for _ in range(n)]
vis = [0]*n
a = list(map(int,input().split()))
v = []
x = [0]
y = []
vis[0] = 1
cur = 0
while x:
    for i in x:
        cur += a[i]
        for j in con[i]:
            if not vis[j]:
                y.append(j)
                vis[j] = 1
    v.append(cur)
    x = y
    y = []
v.append(10**18)
for i in c:
    print(bisect.bisect_left(v,i+1)-1)
```

## 活動 (Event)

> 出題者：C0DET1GER
> 難度：p4
> 考點：貪心、排序、動態規劃
### Statement
APCS 模擬測驗團隊雖然最初是為了舉辦模擬測驗而成立的，但後來因為大家的鼓勵、參與，模擬測驗團隊也開始有辦理其他活動的想法（例如：APCS Camp、實體 APCS 模擬測驗...）。

對於每一個活動，都會有一定的收益（因為 APCS 模擬測驗團隊是一個公益組織，收益有可能為 $0$，甚至是負的）和獲益人數。

APCS 模擬測驗團隊當然希望能夠讓越多人參與越好，但要考量到有些活動會帶來虧損，因此團隊想要在所有可能的舉辦方案中，選擇一個總收益 $\ge 0$ 的方案，且參與人數盡量大。

除此之外，因為時間上的問題，在 $N$ 個活動中至多只能舉辦 $K$ 個相互不重複的活動，否則團隊將會忙到焦頭爛額。

因此模擬測驗團隊希望你能夠幫幫忙，給定 $N$ 個活動的收益和參與人數，請求出在所有可能的舉辦方案中，在總收益 $\ge 0$ 的情況下參與人數總和的最大值（初始資金為 $0$）。
### Input
第一行輸入兩個正整數 $N$ $(1 \leq N \leq 35)$, $K$ $(1 \leq K \leq N)$
接下來輸入 $N$ 行，每一行包含兩個數字：$a_i$ $(-10^7 \leq a_i \leq 10^7)$和 $b_i$ $(0 \leq b_i \leq 100)$，分別代表第 $i$ 個活動的淨收益和獲益人數。
### Output
一個數字，代表 $K$ 個活動（按照任意順序進行）的最大可能收益人數總和。
### Testcase
- Input 1
```
5 3
-50 70
-70 80
100 10
-1 2
-100 100
```
- Output 1
```
110
```
### Subtask
- Subtask 1 (10%)：$N \leq 8$
- Subtask 2 (10%)：$N \leq 20$
- Subtask 3 (30%)：$|a_i| \leq 100$
- Subtask 4 (50%)：題目範圍限制
### Note
最佳解為：先取 3 再取 5。因為題目是說至多 $K$ 個活動，活動數量可以小於 $K$。
### Solution
（此處 $a_i$ 一律代表第 $i$ 個活動的淨收益，$b_i$ 代表第 $i$ 個活動的獲益人數
* Subtask 1：
    * 先暴力枚舉要哪些活動再枚舉所有可能排列。
    * 時間複雜度：$O(2^N \times N!)$
* Subtask 2：
    * 先貪心的將活動按照 $a_i$ 排序再枚舉
    * 時間複雜度：$O(N \log N + 2^N)$
* Subtask 3：
    * 先貪心的將活動按照 $a_i$ 排序
    * 這個 Subtask 開始要使用動態規劃。可以設計狀態 $dp[i][j][k]$，其中 $i$ 代表前 $N$ 個活動、$j$ 代表現在已經舉辦了幾個活動、$k$ 代表現在有多少錢、$dp[i][j][k]$ 代表在考慮前 $i$ 個活動之中辦了 $j$ 個活動、最後有 $k$ 塊錢的時候，參與人數最大可能值。
    * 因為已經預先照 $a_i$ 排序，不會有因為順序錯誤而導致 DP 答案錯誤的問題
    * 轉移：$dp[i][j][k] = max(dp[i - 1][j][k], dp[i - 1][j - 1][k - a_i] + b_i)$
    * 初始化：$dp[i][j][k] = 0$
    * 答案：dp 陣列中的最大值
    * 時間複雜度：$O(N^2 \times \sum{\max(a_i, 0)} )$
* Subtask 4：
    * （人數至多跟 Subtask 3 的 profit 一樣大的提示應該夠大了吧）
    * 先貪心的將活動按照 $a_i$ 排序
    * 發現 $|a_i|$ 的範圍太大了，用原本的方法時間複雜度會炸開。但是可以改變狀態的定義。可以設計狀態 $dp[i][j][k]$，其中 $i$ 代表前 $N$ 個活動、$j$ 代表現在已經舉辦了幾個活動、$k$ 代表現在總共有多少人參與、$dp[i][j][k]$ 代表在考慮前 $i$ 個活動之中辦了 $j$ 個活動、來的人有 $k$ 個的時候，獲利的最大可能值。
    * 轉移：$dp[i][j][k] = \max(dp[i - 1][j][k], dp[i - 1][j - 1][k - b_i] + a_i)$
    * 要注意轉移中如果 $dp[i - 1][j - 1][k - b_i] < 0$，要直接把 $dp[i][j][k]$ 設為 $dp[i - 1][j][k]$
    * 初始化：$dp[0][0][0] = 0$、$dp[i][j][k] = -1$
    * 答案：在所有 $dp[i][j][k] \geq 0$ 中，$k$ 的最大可能值。
    * 時間複雜度：$O(N^2 \times \sum{b_i})$
### Code
- Subtask 1
```cpp=
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    int N, K;
    cin >> N >> K;
    vector<pair<int, int>> event(N);
    for (int i = 0; i < N; i++){
        cin >> event[i].first >> event[i].second;
    }
    int maximum = 0;
    for (int i = 0; i < (1LL << N); i++){
        vector<int> chosen;
        for (int j = 0; j < N; j++){
            if (i & (1 << j)){
                chosen.push_back(j);
            }
        }
        if (chosen.size() <= K){
            do{
                int money = 0, cnt = 0;
                for (int j = 0; j < chosen.size(); j++){
                    money += event[chosen[j]].first;
                    if (money < 0){
                        break;
                    }
                    cnt += event[chosen[j]].second;
                }
                maximum = max(maximum, cnt);
            }while (next_permutation(chosen.begin(), chosen.end()));
        }
    }
    cout << maximum << "\n";
}
```
- Subtask 2
```cpp=
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool cmp(pair<int, int> a, pair<int, int> b){
    return a.first > b.first;
}

int main(){
    int N, K;
    cin >> N >> K;
    vector<pair<int, int>> event(N);
    for (int i = 0; i < N; i++){
        cin >> event[i].first >> event[i].second;
    }
    sort(event.begin(), event.end(), cmp);
    int maximum = 0;
    for (int i = 0; i < (1LL << N); i++){
        int money = 0, cnt = 0, used = 0;
        for (int j = 0; j < N; j++){
            if (i & (1 << j)){
                money += event[j].first;
                if (money < 0){
                    break;
                }
                cnt += event[j].second;
                used++;
            }
        }
        if (used <= K){
            maximum = max(maximum, cnt);
        }
    }
    cout << maximum << "\n";
}
```
- Subtask 3
```cpp=
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
 
bool cmp(pair<int, int> a, pair<int, int> b){
    return a.first > b.first;
}

int main() {
    int N, K;
    cin >> N >> K;
    int sum = 0;
    vector<pair<int, int>> event(N);
    for (int i = 0; i < N; i++){
        cin >> event[i].first >> event[i].second;
        sum += max(event[i].first, 0);
    }
    sort(event.begin(), event.end(), cmp);
    vector<vector<vector<int>>> dp(N + 1, vector<vector<int>>(K + 1, vector<int>(sum + 1, -1)));
    dp[0][0][0] = 0;
    int maximum = 0;
    for (int i = 1; i <= N; i++){
        for (int j = 0; j <= K; j++){
            for (int k = 0; k <= sum; k++){
                dp[i][j][k] = dp[i - 1][j][k];
                if (j != 0 && k >= event[i - 1].first && k <= (sum + event[i - 1].first) && dp[i - 1][j - 1][k - event[i - 1].first] >= 0){
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - 1][k - event[i - 1].first] + event[i - 1].second);
                }
                maximum = max(maximum, dp[i][j][k]);
            }
        }
    }
    cout << maximum << "\n";
}
```
- Subtask 4
``` cpp=
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
 
bool cmp(pair<int, int> a, pair<int, int> b){
    return a.first > b.first;
}

int main() {
    int N, K;
    cin >> N >> K;
    int sum = 0;
    vector<pair<int, int>> event(N);
    for (int i = 0; i < N; i++){
        cin >> event[i].first >> event[i].second;
        sum += event[i].second;
    }
    sort(event.begin(), event.end(), cmp);
    vector<vector<vector<int>>> dp(N + 1, vector<vector<int>>(K + 1, vector<int>(sum + 1, -1)));
    dp[0][0][0] = 0;
    int maximum = 0;
    for (int i = 1; i <= N; i++){
        for (int j = 0; j <= K; j++){
            for (int k = 0; k <= sum; k++){
                dp[i][j][k] = dp[i - 1][j][k];
                if (j != 0 && k >= event[i - 1].second && dp[i - 1][j - 1][k - event[i - 1].second] >= 0){
                    dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - 1][k - event[i - 1].second] + event[i - 1].first);
                }
                if (dp[i][j][k] >= 0){
                    maximum = max(maximum, k);
                }
            }
        }
    }
    cout << maximum << "\n";
}
```
- 折半枚舉 by 橘子
```python=
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll big = 1e18;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n,k;
    cin >> n >> k;
    vector<pair<ll,ll>> a(36,{0,0});
    for(ll i = 0;i<n;i++) cin >> a[i].first >> a[i].second;
    n = 36;
    sort(a.begin(),a.end());
    vector<pair<ll,ll>> b(1<<18,{0,0});
    vector<vector<pair<ll,ll>>> c(19);
    ll ans = 0;
    for(ll i = 1;i<(1<<18);i++){
        b[i] = b[i-(i&-i)];
        ll j = __builtin_ctzll(i);
        b[i].first += a[j].first;
        b[i].second += a[j].second;
        ll cnt = __builtin_popcountll(i);
        if(cnt<=k&&b[i].first>=0) ans = max(ans,b[i].second);
        if(cnt<k){
            for(ll w = cnt;w<=18;w++)c[w].push_back(b[i]);
        }
    }
    for(auto &o : c){
        sort(o.begin(),o.end());
        for(ll i = o.size()-2;i>=0;i--){
            o[i].second = max(o[i].second,o[i+1].second);
        }
    }
    vector<pair<ll,ll>> d(1<<18,{0,0});
    for(ll i = 1;i<(1<<18);i++){
        d[i] = d[i-(i&-i)];
        ll j = __builtin_ctzll(i);
        d[i].first += a[j+18].first;
        d[i].second += a[j+18].second;
        ll cnt = __builtin_popcountll(i);
        if(cnt<=k&&d[i].first>=0) ans = max(ans,d[i].second);
        if(cnt<k&&k-cnt<=18){
            auto &o = c[k-cnt];
            if(o.empty()) continue;
            auto it = lower_bound(o.begin(),o.end(),make_pair(-d[i].first,0ll));
            if (it!=o.end()){
                ans = max(ans,d[i].second+(*it).second);
            }
        }
    }
    cout << ans << "\n";
}
```
- Python by 橘子
```python=
def main():
    n, k = map(int,input().split())
    a = [tuple(map(int,input().split())) for _ in range(n)]
    a.sort(reverse=True)
    dp = [[-10**10]*3505 for _ in range(k+1)]
    dp[0][0] = 0
    ed = [0]*(k+1)
    for x, y in a:
        for i in range(k,0,-1):
            ed[i] = max(ed[i],ed[i-1]+y)
            arr1 = dp[i]
            arr2 = dp[i-1]
            for j in range(y,3502):
                arr1[j] = max(arr1[j],arr2[j-y]+x)
    ans = 0
    for j in range(k,0,-1):
        arr = dp[j]
        for i in range(ed[j],ans,-1):
            if arr[i]>=0:
                ans = max(ans,i)
    print(ans)
main()
```