Array Division

    1#include <bits/stdc++.h>
    2using namespace std;
    3typedef long long ll;
    4const int MM = 1e5 + 5;
    5int n, m, a[MM];
    6bool check(ll lmt){
    7    ll sum = 0; int cnt = 1;
    8    for(int i = 1; i <= n; i++){
    9        if(sum + a[i] > lmt){
    10            sum = a[i]; cnt++;
    11        } else {
    12            sum += a[i];
    13        }
    14    }
    15    return cnt <= m;
    16}
    17int main(){
    18    ios::sync_with_stdio(0); cin.tie(0);
    19    cin >> n >> m;
    20    ll lo = 0, hi = 0, ans = 0;
    21    for(int i = 1; i <= n; i++){
    22        cin >> a[i]; lo = max((ll)a[i], lo); hi += a[i];
    23    }
    24    while(lo <= hi){
    25        ll mid = (lo + hi) / 2;
    26        if(check(mid)){
    27            ans = mid;
    28            hi = mid - 1;
    29        } else {
    30            lo = mid + 1;
    31        }
    32    }
    33    cout << ans << '\n';
    34    return 0;
    35}