Small L's test paper

 

Title Description

Small L The final exam is over , Happy holiday home , But so many papers , The teacher has to work overtime to correct , Yes n This paper consists of k A teacher corrects ,n The papers were sealed and numbered , Due to the difference between the standard procedure of writing and the situation of making questions on the test paper , It may take different time to correct different test papers , The numbering sequence of each teacher's correcting papers is continuous , Each teacher can leave after correcting the assigned test paper , Ask the teacher who left last , What is the shortest possible time , Suppose that when any teacher corrects an exam paper, it is the same . Now please design a distribution scheme , Make the last teacher to leave the shortest time . 

Input

The first line has two integers n,k;（0<k≤n≤1000） 

The second line n It's an integer , The first i An integer indicates the correction number i Time of examination papers . 

Output

Output an integer , It means the shortest time for the last teacher to leave

The sample input  Copy

9 3                              
1 2 3 4 5 6 7 8 9

Sample output  Copy

17

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f;
const int maxn = 1e5 + 10;

int n , k;
ll a[maxn];

bool isok(int x)
{
    bool flag = false;
    int num = 0;
    ll temp = 0;
    for (int i=1; i<=n; i++)
    {
        if (a[i] > x)  return false;
        temp += a[i];
        if (temp > x)
        {
            num ++;
            temp = a[i];
        }
    }
    if (temp > 0)  num ++;
    if (num <= k)  return true;
    else  return false;
}
int main()
{
    scanf("%d%d", &n, &k);
    for (int i=1; i<=n; i++)  scanf("%lld", &a[i]);
    ll l = 0 , r = inf;
    while (l <= r)
    {
        int mid = (l + r) / 2;
        if (isok(mid))  r = mid-1;
        else  l = mid + 1;
    }

    cout << l << endl;
    return 0;
}