TOI10 CrazyAdmin

#include <bits/stdc++.h>


using namespace std;

int package(int n ,int room[] ,int cap){
    int adsl_cnt = 1 ,curr_sum = 0;
    for(int i=0;i<n;++i){
        if (room[i] > cap){
            return 1000000;
        }
        if(room[i]+curr_sum>cap){
            ++adsl_cnt;
            curr_sum = 0;
        }
        curr_sum+= room[i];
    }
    return adsl_cnt;
}

int findcap(int n , int room[] ,int k){
    int max_room = 0, sum=0;
    for(int i=0;i<n;++i){
        if(max_room<room[i]){
            max_room = room[i];
        }
        sum = sum + room[i];
    }

    int l = max_room , r = sum , ans =sum;
    while(l<=r){
        int m = (l+r)/2;
        if(package(n,room,m)> k){
            l = m+1;
        }
        else{
            if(m<ans){
                ans = m;
            }
            r= m-1;
        }
    }

    return ans;
}
int main(){
    int m ,o;
    scanf("%d%d",&m,&o);
    int room[o+1];
    for(int i=0;i<o;++i){
        scanf("%d",&room[i]);
    }
    cout << findcap(o,room,m);

    return 0;
}