HW4A

#include <iostream>
#include <vector>

using namespace std;

bool mid_sum_check(vector <int> const & V,  int N, int K, int mid_sum) {
    int count = 1;
    int sum = 0;

    for (int i = 0; i < N; i++) {
        if (V[i] > mid_sum)
            return false;

        sum += V[i];

        if (sum > mid_sum) {
            count++;
            sum = V[i];
        }
    }

    return (count <= K) ? true : false;
}

int min_sum(vector <int> const & V, int N, int K) {
    int L = 1;
    int R = 0;
    for (int i = 0; i < N; i++) {
        R += V[i];
    }

    int answer = 0;
    while (L <= R) {
        int mid_sum = R - (R - L) / 2;
        if (mid_sum_check(V, N, K, mid_sum)) {
            answer = mid_sum;
            R = mid_sum - 1;
        }
        else {
            L = mid_sum + 1;
        }
    }
    return answer;
}

int main()
{
    int K, N;
    cin >> K >> N;

    vector <int> V (N);
    for (int i = 0; i < N; i++)
        cin >> V[i];

    int sum = min_sum(V, N, K);
    cout << sum;
}