小米B最优分割

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <math.h>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#pragma warning(disable:4996)

#define Zero(a) memset(a, 0, sizeof(a))
#define Neg(a)  memset(a, -1, sizeof(a))
#define All(a) a.begin(), a.end()
#define PB push_back
#define repf(i,a,b) for(i = a;i <= b; i++)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define root 1,n,1
#define ld rt << 1
#define rd rt << 1 | 1
#define ll long long
#define MAXN 1010
#define mod 1000000007
#define inv2 500000004
#define sqrtt(x) (ll)(x)*(x)
#define dist(x1,y1,x2,y2) (sqrtt(x1-x2)+sqrtt(y1-y2))

using namespace std;
vector<ll>nums;
bool can_split(int m, ll sum) {
int cnt = 1;
ll curSum = 0;
for (int i = 0; i < nums.size(); ++i) {
curSum += nums[i];
if (curSum > sum) {
curSum = nums[i];
++cnt;
if (cnt > m) return false;
}
}
return true;
}
ll splitArray(int m) {
long long left = 0, right = 0;
for (int i = 0; i < nums.size(); ++i) {
left = max(left, nums[i]);
right += nums[i];
}
while (left < right) {
long long mid = (left + right) / 2;
if (can_split(m, mid)) right = mid;
else left = mid + (ll)1;
}
return left;
}
int n, m;
int main(){
ll dd;
//freopen("in.txt","r", stdin);
//freopen("out.txt", "w", stdout);
ios::sync_with_stdio(false);
while (cin >> n >> m) {
nums.clear();
for (int i = 0; i < n; ++i) {
cin >> dd;
nums.push_back(dd);
}
ll ans;
ans = splitArray(m);
cout << ans << endl;
}
return 0;
}
#小米#