TOI10: Crazy Admin

#include <iostream>
#include <vector>
using namespace std;

#define lli long long

vector<int> rooms;
int nw, nr;

int main(){

    int x;

    scanf("%d %d", &nw, &nr);
    rooms.assign(nr + 1, 0);
    for(int i = 1; i <= nr; ++i){
        scanf("%d", &x);
        rooms[i] = x;
    }

    int l = 1;
    int r = 150000;
    int ans = 150000;
    while(l <= r){
        int m = (l + r) / 2;
        int cnt = 1;
        int sum = 0;
        int mx = 0;
        for(int i = 1; i <= nr; ++i){
            if(sum + rooms[i] <= m){
                sum += rooms[i];
            } else {
                mx = max(mx, sum);
                sum = rooms[i];
                ++cnt;
            }
        }
        mx = max(mx, sum);
        if(cnt > nw){
            l = m + 1;
        } else {
            ans = min(ans, mx);
            r = m - 1;
        }
    }

    cout << ans;

    return 0;
}