43 lines
877 B
C++
43 lines
877 B
C++
// Array Division
|
|
|
|
#include<bits/stdc++.h>
|
|
|
|
using namespace std;
|
|
using ll = long long;
|
|
|
|
bool check_sum(vector<ll> &a, ll target_sum, int max_number_of_sub_arrays) {
|
|
ll sum = 0;
|
|
ll count = 1;
|
|
for (int i{}; i < a.size(); i++) {
|
|
if (sum + a[i] <= target_sum) {
|
|
sum += a[i];
|
|
} else {
|
|
sum = a[i];
|
|
if (sum > target_sum) return false;
|
|
count++;
|
|
}
|
|
}
|
|
return count <= max_number_of_sub_arrays;
|
|
}
|
|
|
|
int main() {
|
|
int n, k; cin >> n >> k;
|
|
vector<ll> a(n);
|
|
ll sum = 0;
|
|
for (int i{}; i < n; i++) {
|
|
cin >> a[i];
|
|
sum += a[i];
|
|
}
|
|
ll lo = 0;
|
|
ll hi = INT64_MAX / 3;
|
|
while (lo < hi) {
|
|
ll mid = (lo + hi) / 2;
|
|
if (check_sum(a, mid, k)) {
|
|
hi = mid;
|
|
} else {
|
|
lo = mid + 1;
|
|
}
|
|
}
|
|
cout << lo << endl;
|
|
}
|