# SOLUTION CONTEST XUÂN ẤT TỴ 2025

## Chúc mừng năm mới
Đề cho xâu ký tự "chuc mung nam moi" được nhập vào mảng $a[]$ nhưng lại có 2 điều kiện:
- Không đảm bảo thứ tự chính xác của xâu.
- Các ký tự được viết in hoa/in thường một cách ngẫu nhiên.

Do đó, để sắp xếp được 4 string đề cho thành câu có dạng "chuc mung nam moi" thì ta phải thực hiện 2 bước sau:

- Tạo một bản copy của câu đề cho và chuyển tất cả thành ký tự in thường gọi bản copy là mảng $b[]$
- Xét lần lượt các xâu **"chuc", "mung", "nam", "moi"** và kiểm tra xem ở bản copy thì xâu nào ở mảng $b$ giống với các xâu trên sau đó xuất xâu đại diện của xâu đó ở mảng $a$.

**Cài đặt (tham khảo)**

#include <bits/stdc++.h>
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define TASK "test"

using namespace std;

int32_t main(){
    fastIO;
    // file(TASK);

    vector<string> a(4), b(4);
    for(int i=0; i<4; i++) cin >> a[i], b[i] = a[i];
    for(int i=0; i<4; i++) for(char &c: b[i]) if(c < 'a') c += 'a' - 'A';
    string d[] = {"chuc", "mung", "nam", "moi"};
    for(int i=0; i<4; i++){
        for(int j=0; j<4; j++){
            if(b[j] == d[i]) cout << a[j] << ' ';
        }
    }

    return 0;
}

---

## Ma trận
Tóm tắt đề: cho ma trận $n*m$ gồm các số 0 và 1. Tìm bảng con hình vuông lớn nhất sao cho chỉ chứa số 1.

Gọi $dp[i][j]$ là độ lớn cạnh hình vuông lớn nhất thỏa mãn điều kiện đề bài của hình vuông có góc phải dưới là ô $(i, j)$

Chia 2 trường hợp:
- $a[i][j] = 1 \Rightarrow dp[i][j] = min({dp[i-1][j], dp[i][j-1], d[i-1][j-1]}) + 1$
- $a[i][j] = 0 \Rightarrow dp[i][j] = 0$

#include <bits/stdc++.h>
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)

using namespace std;
const int MX = 1005;

int n, m;
int a[MX][MX];

int32_t main(){
    fastIO;

    cin >> n >> m;
    int ans = 0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            cin >> a[i][j];
            if(a[i][j] == 0) continue;
            a[i][j] = min({a[i-1][j], a[i][j-1], a[i-1][j-1]}) + 1;
            ans = max(ans, a[i][j]);
        }
    }   
    cout << ans;

    return 0;
}

---

## Tổng lớn nhất
Tóm tắt đề: cho 2 dãy $A$, $B$ gồm $N$, $M$ phần tử, mảng 2 chiều C gồm $N*M$ phần tử, $C[i][j] = A[i] * B[j]$. Tìm bảng con có tổng lớn nhất.

Bằng một vài phép toán cơ bản, ta có thể rút ra công thức để tính tổng một bảng con có ô trái trên là $(x, y)$ ô phải dưới là $(u, v)$ theo công thức sau:
- $Sum(x, y, u, v) = (A[x] + A[x + 1] + \ldots + A[u]) * (B[y] + B[y + 1] + \ldots + B[v])$

Khi đó tổng của bảng con sẽ được biểu diễn bởi tích của tổng 2 dãy con liên tiếp trong A và B, do đó ta sẽ xét 2 trường hợp:
- $ans = maxSumA * maxSumB$
- $ans = minSumA * minSumB$
với $maxSumA,~maxSumB,~minSumA,~minSumB$ lần lượt là tổng của dãy con liên tiếp có tổng lớn nhất và bé nhất trong 2 dãy A, B.

Trong trường hợp không tồn tại đáp án là số nguyên không âm, trường hợp:
- $A_i < 0 (1 \leq i \leq N)$ và $B_i > 0 (1 \leq i \leq M)$
- $A_i > 0 (1 \leq i \leq N)$ và $B_i < 0 (1 \leq i \leq M)$

Thì ta phải lấy ở mảng số âm một số âm lớn nhất và lấy ở mảng số dương một số dương bé nhất, kết quả bài toán là tích của hai số đó.

Cài đặt (tham khảo)

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int OO = 1e18;
const int MX = 100005;

int n, m;
int a[MX];
int b[MX];

int32_t main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);

    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=1; i<=m; i++) cin >> b[i];

    bool okA[2] = {0};
    bool okB[2] = {0};
    for(int i=1; i<=n; i++){
        if(a[i] >= 0) okA[0] = 1;
        if(a[i] <= 0) okB[1] = 1;
    }
    for(int i=1; i<=m; i++){
        if(b[i] >= 0) okB[0] = 1;
        if(b[i] >= 0) okB[1] = 1;
    }
    
    if(okA[0] && !okA[1]){
        if(!okB[0] && okB[1]){
            sort(a + 1, a + 1 + n);
            sort(b + 1, b + 1 + m);
            cout << a[1] * b[m];
            return 0;
        }
    }
    if(!okA[0] && okA[1]){
        if(okB[0] && !okB[1]){
            sort(a + 1, a + 1 + n);
            sort(b + 1, b + 1 + m);
            cout << a[n] * b[1];
            return 0;   
        }
    }

    int A[2] = {-OO, OO};
    int _A[2] = {0, 0};
    int B[2] = {-OO, OO};
    int _B[2] = {0, 0};

    for(int i=1; i<=n; i++){
        a[i] += a[i-1];
        A[0] = max(A[0], a[i] - _A[0]);
        A[1] = min(A[1], a[i] - _A[1]);
        _A[0] = min(_A[0], a[i]); _A[1] = max(_A[1], a[i]);
    }
    for(int i=1; i<=m; i++){
        b[i] += b[i-1];
        B[0] = max(B[0], b[i] - _B[0]);
        B[1] = min(B[1], b[i] - _B[1]);
        _B[0] = min(_B[0], b[i]); _B[1] = max(_B[1], b[i]);
    }
    
    cout << max(A[0]*B[0], A[1]*B[1]);
    
    return 0;
}

---

## Bài 4: Đỗ sữa MILK
Chú Ba vừa nhận được một đơn đặt hàng sữa với số lượng chính xác là $M$ lít ($1 ≤ M ≤ 200$) và cần giao ngay cho khách.Tuy nhiên, máy vắt sữa hiện đại của chú bị hỏng, và tất cả những gì chú có là hai thùng sữa có kích thước $X$ và $Y$ lít ($1 ≤ X, Y ≤ 100$). Ban đầu, cả hai thùng đều trống rỗng. Sử dụng hai thùng này, chú Ba có thể thực hiện tối đa K lần các thao tác sau ($1 ≤ K ≤ 100$):  

* Đổ đầy một trong hai thùng.  
* Làm trống một trong hai thùng.  
* Đổ sữa từ thùng này sang thùng kia cho đến khi thùng này hết sữa hoặc thùng kia đầy (tùy điều kiện nào xảy ra trước).  

Chú Ba nhận ra rằng có thể không thể có được chính xác $M$ lít sữa trong hai thùng, vì vậy hãy giúp chú tính toán lượng sai số nhỏ nhất giữa $M$ và tổng lượng sữa trong hai thùng. Nói cách khác, hãy tính giá trị nhỏ nhất của $|M - M'|$ sao cho chú Ba có thể tạo ra được $M'$ lít sữa bằng cách sử dụng hai thùng trên.  

### Input:

- **Dòng đầu tiên và duy nhất** chứa bốn số nguyên chứa $X$, $Y$, $K$ và $M$.

### Output:

- In ra khoảng cách nhỏ nhất từ $M$ đến lượng sữa mà chú Ba có thể tạo ra.

#### Sample Input 1:

14 50 2 32

#### Sample Output 1:

18

#### Giải thích:

Trong hai bước, chú Ba có thể có các lượng sữa sau trong hai thùng:

- $(0, 0) = 0$ lít  
- $(14, 0) = 14$ lít
- $(0, 14) = 14$ lít
- $(0, 50) = 50$ lít
- $(14, 36) = 50$ lít
- $(14, 50) = 64$ lít

Lượng sữa gần nhất với $32$ lít mà chú Ba có thể tạo ra là $14$ lít, với sai số là $18$.

### Ý tưởng
>[!Note] Kiến thức cần
> Loang

Giả sử ta đang có trạng thái bài toán như sau
- Thùng thứ 1 đang có $A$ lít sữa
- Thùng thứ 2 đang có $B$ lít sữa
- Ta đã thực hiện được $C$

$\rightarrow$ Gọi tắt là $(A, B, C)$
>[!Important]
>$0 \le A \le X$
>$0 \le B \le Y$
>$0 \le C \le K$

Dễ thấy, từ trạng thái này ta có thể thực hiện các thao tác có thể để có thể đến được các trạng thái:

* $(0, B, C + 1)$
>Làm trống thùng 1
* $(A, 0, C + 1)$
>Làm trống thùng 2
* $(X, B, C + 1)$
>Đổ đầy thùng 1
* $(A, Y, C + 1)$
>Đổ đầy thùng 2
* $(A + B - \min(A + B, Y),\space \min(A + B, Y),\space C + 1)$
>Đổ từ thùng 1 sang thùng 2
* $(\min(A + B, X),\space A + B - \min(A + B, X), \space C + 1)$
>Đổ từ thùng 2 sang thùng 1

Tổng số trạng thái tối đa là $X \times Y \times K$, mỗi trạng thái có $6$ cách để qua trạng thái mới.

$\Rightarrow$ Do đó độ phức tạp để loang qua hết tất cả các trạng thái là $O(6 * X * Y * K)$

Vì vậy, để giải quyết bài toán, ta chỉ cần tìm trạng thái $(A, B, C)$ có thể loang tới mà $|(A + B) - M|$ là bé nhất

### Code

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

int vis[201][201][201];
int X, Y, K, M;
int ans = 10000000;

void dfs(const int& A, const int& B, const int& C) {
    if (C > K || vis[A][B][C]) return;
    vis[A][B][C] = 1;
    ans = min(ans, abs(A + B - M));
    dfs(0, B, C + 1); //Làm trống thùng 1
    dfs(A, 0, C + 1); //Làm trống thùng 2
    dfs(X, B, C + 1); //Đổ đầy thùng 1
    dfs(A, Y, C + 1); //Đổ đầy thùng 2
    dfs(A + B - min(A + B, Y), min(A + B, Y), C + 1); //Đổ từ thùng 1 sang thùng 2
    dfs(min(A + B, X), A + B - min(A + B, X), C + 1); //Đổ từ thùng 2 sang thùng 1
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> X >> Y >> K >> M;
    dfs(0, 0, 0);
    cout << ans;
}

---

## Bài 5: Đến trường SCHOOL
Ngôi làng An Bình nằm yên bình bên dòng sông xanh mát. Cuộc sống nơi đây tuy giản dị nhưng tràn đầy niềm vui. Trẻ em trong làng đều ham học hỏi, nhưng trường học hiện tại lại nằm khá xa, gây khó khăn cho việc đi lại. Ông trưởng làng, một người luôn tâm huyết với sự phát triển của thế hệ trẻ, quyết định xây dựng thêm trường học để các em có điều kiện học tập tốt hơn.

Tuy nhiên, việc xây dựng trường học ở đâu để thuận tiện cho mọi người lại là một bài toán nan giải. Làng An Bình có $n$ ngôi nhà nằm dọc theo con đường chính, mỗi ngôi nhà được đánh số từ $1$ đến $n$. Khoảng cách giữa hai ngôi nhà $a$ và $b$ được tính bằng giá trị tuyệt đối của hiệu số giữa chúng: $|a - b|$. Ông trưởng làng đã khảo sát và biết được số lượng trẻ em ở mỗi ngôi nhà.

Ông muốn xây dựng $k$ trường học sao cho mỗi trường đều nằm trong một ngôi nhà. Sau khi trường học được xây dựng, mỗi đứa trẻ sẽ đi bộ đến trường gần nhất. Ông trưởng làng mong muốn tìm ra cách xây dựng trường học sao cho tổng quãng đường đi bộ của tất cả trẻ em là nhỏ nhất có thể.

**Nhiệm vụ của bạn**:

Hãy giúp ông trưởng làng tính toán khoảng cách tối thiểu mà các em nhỏ phải đi bộ nếu ông ấy lựa chọn vị trí xây dựng trường học một cách tối ưu.

### Input:

- **Dòng đầu tiên** chứa hai số nguyên $n$ và $k$, lần lượt là số lượng ngôi nhà và số lượng trường học cần xây dựng. $(n ≤ 3000, k \le 2)$
- **Dòng thứ hai** chứa $n$ số nguyên $c_1, c_2,..., c_n$ biểu thị số lượng trẻ em ở mỗi ngôi nhà. $(1 ≤ c_i ≤ 10000)$

### Output:

- In ra tổng khoảng cách tối thiểu mà các em nhỏ phải đi bộ.

### Rằng buộc:
- Subtask $1$: $50\%$ số test có $k = 1$
- Subtask $2$: $50\%$ số test còn lại không có rằng buộc gì thêm

### Sample Input 1:

6 2
2 7 1 4 6 4

### Sample Output 1:

11

#### Giải thích:

Trong ví dụ này, nếu xây dựng trường học ở ngôi nhà số $2$ và $5$, tổng quãng đường đi bộ của các em nhỏ sẽ là nhỏ nhất $(11)$.

### Ý tưởng
#### Trường hợp $k = 1$

Với $k = 1$, giả sử ngôi nhà được chọn là $u$, ta có thể dễ dàng tính được tổng quãng đường để đến $u$ thông qua việc duyệt qua từng ngôi nhà còn lại và cộng vào tổng $sum = sum + c_i * |i - u|$

Vậy ta chỉ cần duyệt qua từng $u$ từ $1 \rightarrow n$, với mỗi $u$ tính tổng quãng đường đến đó

ĐPT $O(n^2)$

#### Trường hợp $k = 2$

Ý tưởng cơ bản: khi ngôi nhà được là $u$ và $v$ ta có thể tính nhanh tổng đường đi đến $u$ và $v$.

**Gọi:**
$\rightarrow pfs[i]$ là tổng quảng đường để các ngôi nhà $[1, i - 1]$ đi về **bên phải** đến $i$
$\rightarrow pfsl[i]$ là tổng số lượng các em nhỏ $[1, i]$

**Ta có:**
* $pfs[i] = pfs[i - 1] + pfsl[i - 1]$
* $pfsl[i] = pfsl[i - 1] + c_i$

**Gọi**

$\rightarrow sfs[i]$ là tổng quảng đường để các ngôi nhà $[v + 1, n]$ đi về **bên trái** đến $i$
$\rightarrow sfsl[i]$ là tổng số lượng các em nhỏ $[i, n]$

**Ta có:**
* $sfs[i] = sfs[i + 1] + sfsl[i + 1]$
* $sfsl[i] = sfsl[i + 1] + c_i$

Gọi $mid$ với $mid = (u + v) / 2$ là điểm nằm giữa $u$ và $v$ dễ thấy:
* Các ngôi nhà $[1, u - 1]$ sẽ di chuyển về **bên phải** đến $u$

$\Rightarrow$ Tổng quãng đường ==$= pfs[u]$==

* Các ngôi nhà $[mid + 1, v - 1]$ sẽ di chuyển về **bên phải** đến $v$

$\Rightarrow$ Tổng quãng đường ==$= pfs[v] - pfs[mid] - pfsl[mid] \times (v - mid)$==

* Các ngôi nhà $[v + 1, n]$ sẽ di chuyển về **bên trái** đến $v$

$\Rightarrow$ Tổng quãng đường ==$= sfs[v]$==

* Các ngôi nhà $[u + 1, mid]$ sẽ di chuyển về **bên trái** đến $u$

$\Rightarrow$ Tổng quãng đường ==$= sfs[u] - sfs[mid + 1] - sfsl[mid + 1] \times (mid + 1 - u)$==

Vậy khi 2 ngôi nhà được chọn là $u$ và $v$ ta có tổng quãng đường mà trẻ nhỏ phải đến là:

==$pfs[u] + pfs[v] - pfs[mid] - pfsl[mid] \times (v - mid)$
$+$
$sfs[v] + sfs[u] - sfs[mid + 1] - sfsl[mid + 1] \times (mid + 1 - u)$==

Do đó, để giải quyết trường hợp $k = 2$ ta chỉ cần duyệt mọi cặp $u, v$ và tính theo công thức trên

ĐPT $O(n ^ 2)$

>[!Tip]
>Nếu sử dụng Convex Hull Trick ta còn có thể tối ưu bài toán xuống còn $O(n \times k)$ với mọi $k$
>Bài toán gốc https://cses.fi/problemset/task/2087

### Code

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

int c[1000001];
int pfs[1000001];
int pfsl[1000001];
int sfs[1000001];
int sfsl[1000001];

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> c[i];
    int ans = 1e18;
    if (k == 1) {
        for (int u = 1; u <= n; u++) {
            int sum = 0;
            for (int i = 1; i <= n; i++) {
                sum += c[i] * abs(i - u);
            }
            ans = min(ans, sum);
        }
    }
    else {
        for (int i = 1; i <= n; i++) {
            pfs[i] = pfs[i - 1] + pfsl[i - 1];
            pfsl[i] = pfsl[i - 1] + c[i];
        }
        for (int i = n; i >= 1; i--) {
            sfs[i] = sfs[i + 1] + sfsl[i + 1];
            sfsl[i] = sfsl[i + 1] + c[i];
        }
        for (int u = 1; u <= n; u++) {
            for (int v = 1; v <= n; v++) {
                const int mid = (u + v) / 2;
                int sum = pfs[u] + pfs[v] - pfs[mid] - pfsl[mid] * (v - mid);
                sum += sfs[v] + sfs[u] - sfs[mid + 1] - sfsl[mid + 1] * (mid + 1 - u);
                ans = min(ans, sum);
            }
        }
    }
    cout << ans << '\n';
}

---

## Bài 6: Hái mọng BERRIES
Hai chị em, Bé và An, cùng nhau ra vườn mọng của bác Ba để hái quả. Vườn mọng của bác Ba có rất nhiều cây, mỗi cây trĩu quả với đủ loại to nhỏ. Cả Bé và An đều rất thích ăn quả mọng, nhưng bác Ba có một quy định: mỗi người chỉ được hái quả vào một số lượng giỏ nhất định, và mỗi giỏ chỉ được đựng quả từ một cây duy nhất.

Bé là chị cả nên được mang theo nhiều giỏ hơn An. Cô bé muốn hái được thật nhiều quả mọng. Tuy nhiên, vì là chị nên Bé cũng phải chia sẻ một nửa số giỏ của mình cho An, và An sẽ được chọn những giỏ có nhiều quả nhất. Điều này có nghĩa là An có thể sẽ có nhiều quả mọng hơn Bé, mặc dù Bé đã cố gắng hái rất nhiều.

Bé cảm thấy hơi thiệt thòi, nhưng cô bé vẫn muốn hái được nhiều quả mọng nhất có thể. Bạn hãy giúp Bé tính toán xem cô bé có thể hái được tối đa bao nhiêu quả mọng nhé!

Vườn mọng của bác Ba có $N$ cây mọng $(1 ≤ N ≤ 1000)$. Cây thứ $i$ có $B_i$ quả mọng $(1 ≤ B_i ≤ 1000)$. Bé có $K$ giỏ ($1 ≤ K ≤ 1000$, $K$ là số chẵn). Mỗi giỏ có thể đựng được nhiều quả mọng từ cùng một cây, nhưng không được đựng quả từ các cây khác nhau. Bé phải đưa cho An $K/2$ giỏ có số quả mọng nhiều nhất.

Hãy giúp Bé xác định số quả mọng tối đa mà cô bé có thể hái được.

### Input:

- **Dòng đầu tiên** chứa hai số nguyên $N$ và $K$, cách nhau bởi dấu cách.
- **Dòng thứ hai** chứa $N$ số nguyên $B_1, B_2,..., B_N$, cách nhau bởi dấu cách.

### Output:

- Một dòng duy nhất chứa số quả mọng tối đa mà Bé có thể hái được.

### Rằng buộc:

- Subtask $1$: $50\%$ số test có $k \le 10$
- Subtask $2$: $50\%$ số test còn lại không có rằng buộc gì thêm

#### Sample Input 1:

5 4
3 6 8 4 2

#### Sample Output 1:

8

#### Giải thích:

Bé có thể hái $4$ quả từ cây thứ $2$ vào một giỏ, $4$ quả từ cây thứ $3$ vào hai giỏ, và $4$ quả từ cây thứ $4$ vào một giỏ. Sau đó, Bé sẽ đưa cho An hai giỏ, mỗi giỏ có $4$ quả dâu, và Bé sẽ giữ lại hai giỏ còn lại, cũng có tổng cộng $8$ quả dâu.

### Ý tưởng

>[!Note] Kiến thức cần
>Tham lam

#### **Trường hợp $K$ nhỏ:**
Sau khi sắp xếp các cây theo **số lượng quả giảm dần**, chúng ta không cần phải xét các cây nằm ngoài **$K$ cây đầu tiên**.
Hơn nữa, nếu chúng ta quyết định chọn **$x$** giỏ từ cây thứ **$i$**, thì mỗi giỏ nên có **hoặc** $\lfloor B_i / x \rfloor$ **hoặc** $\lfloor B_i / x \rfloor + 1$ quả.
Dựa vào các quan sát này, ta có thể áp dụng một **thuật toán quay lui (backtracking).**

#### **Lời giải đầy đủ**
Giả sử **$b$** là số lượng quả tối thiểu trong **một trong các giỏ** mà An nhận được.
Không mất tính tổng quát, ta có thể giả định rằng **tất cả giỏ của An** đều chứa **chính xác $b$ quả**.

Lúc này, mục tiêu của chúng ta là **tối đa hóa số lượng quả** mà Bé nhận được bằng cách điền **$K$ giỏ** với **số lượng quả tối đa $b$**, đảm bảo rằng **ít nhất $K/2$ giỏ** có **chính xác $b$ quả**.

#### **Phân bổ quả từ một cây vào các giỏ**
Xét một cây có số lượng quả là **$B_i$**:
- Chúng ta không có lý do gì để tạo ra **nhiều giỏ có ít hơn $b$ quả** từ cây này.
- Vì vậy, tất cả các giỏ sẽ có **chính xác $b$ quả**, ngoại trừ **tối đa một giỏ có thể có ít hơn $b$ quả**.

#### **Chiến lược điền giỏ**
Cách điền giỏ tối ưu:
1. **Lặp lại quá trình điền giỏ có kích thước b** đến khi hết giỏ hoặc tất cả cây còn ít hơn **b** quả.
2. Nếu vẫn còn giỏ trống, sắp xếp các cây còn lại theo **số quả dư (mod $b$)** và **lấy từ nhiều nhất đến ít nhất**.

#### **Độ phức tạp**
- Chạy thuật toán cho mỗi giá trị **$b$** từ **$1$ đến $\max(B_i)$**.
- Sắp xếp danh sách có độ phức tạp **$O(N \log N)$**.
- Tổng thời gian chạy là **$O(\max(B_i) \cdot N \log N)$**.

### Code

#include <bits/stdc++.h>
using namespace std;
 
int N, K;
int A[100000];
int mod;
 
bool cmp(int a, int b) {
    return (a % mod) > (b % mod);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> K;
    
    int M = 0;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        M = max(M, A[i]);
    }

    int best = 0;
    for (int b = 1; b <= M; b++) {
        int full = 0;
        for (int i = 0; i < N; i++)
            full += A[i] / b;

        if (full < K / 2)
            break;
        if (full >= K) {
            best = max(best, b * (K / 2));
            continue;
        }

        mod = b;
        sort(A, A + N, cmp);
        int cur = b * (full - K / 2);
        for (int i = 0; i < N && i + full < K; i++)
            cur += A[i] % b;
        
        best = max(best, cur);
    }
    
    cout << best << '\n';
}

### **Giải thích code**
1. **Đọc dữ liệu đầu vào** và tìm giá trị lớn nhất **$M$** của **$B_i$**.
2. **Duyệt giá trị $b$ từ $1$ đến $M$**:
- Tính tổng số giỏ đầy đủ có thể tạo với **$b$** quả.
- Nếu không thể đủ **$K/2$ giỏ**, dừng vòng lặp.
- Nếu có đủ **$K$ giỏ**, cập nhật kết quả tốt nhất.
- Sắp xếp danh sách cây theo **phần dư mod $b$** và tính số quả tối đa Bessie có thể nhận.
3. **In ra kết quả tối ưu**.