.giúp mik bài này với mn

Ý tưởng

Ta gọi số nguyên $x$ là số thỏa mãn nếu như tồn tại một phương án đi sao cho độ dài quãng đường đi trong ngày đi nhiều nhất trong $m$ ngày không vượt quá $x$.

Dễ thấy, nếu như số $x$ là số thỏa mãn thì $x+1$ cũng sẽ là số thỏa mãn. Ngược lại, nếu như $x$ không phải số thỏa mãn thì $x-1$ cũng không phải số thỏa mãn. Như vậy, ta sẽ có thể dùng thuật toán tìm kiếm nhị phân để tìm ra số thỏa mãn bé nhất. Đó chính là đáp án.

Như vậy, vấn đề còn lại của chúng ta là làm thế nào để kiểm tra một số nguyên $x$ có là số thỏa mãn hay không. Điều đó có nghĩa rằng ta phải kiểm tra với một số $x$, có thể tách dãy số đã cho thành $m$ đoạn liên tiếp sao cho tổng lớn nhất của các phần tử trong một đoạn bé hơn $x$.

Để làm việc này, ta sẽ dùng thuật toán tham lam để thêm từng $d_i$ vào mỗi đoạn. Xét đoạn $\ldots, d_{i-1}$ có tổng các phần tử là $k$. Nếu như $k + d_i \leq x$, ta sẽ thêm $d_i$ vào đoạn này, nếu không ta sẽ tạo một đoạn mới. Ta đếm số đoạn được tạo ra rồi so sánh nó với $m$.

Code (C++ - Chưa mở file)

#include <bits/stdc++.h>
#define __file_name ""
using namespace std;
const int maxn = 1e6+5;

int n,m,a[maxn],l,r,mid,sum;

bool check(int x){
    int cursum = 0,parts = 0;
    for(int i=1;i<=n;i++){
        cursum += a[i];
        if(cursum > x){
            cursum = a[i];
            parts++;
        }
    }
    parts++;
    return (parts <= m);
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    if(__file_name != ""){
        freopen(__file_name ".inp","r",stdin);
        freopen(__file_name ".out","w",stdout);
    }

    cin >> n >> m;
    n++; sum = 0;
    for(int i=1;i<=n;i++) {
        cin >> a[i];
        sum += a[i];
    }
    l = 1; r = sum;
    while(l <= r){
        mid = (l+r)/2;
        if(check(mid)){
            r = mid-1;
        }else{
            l = mid+1;
        }
    }
    cout << l;
    return 0;
}