Cerința

Alex este un copil destul de bun la informatica însă are un defect: Poate fi foarte enervant(prin enervant se înțelege ca își stresează profesorii cu mesaje pe Messenger). Profesorul de informatica s-a săturat de această situație așa ca i-a spus lui Alex ca dacă nu rezolvă următoarea problema îl va bloca pe Messenger. Alex nu vrea sa se întâmple acest lucru deoarece așa e conștient ca nu va mai avea pe cine stresa. Problema sună așa:

Avem n cutii așezate într-o stivă astfel încât avem acces doar la prima cutie.Pentru fiecare cutie sa știe un număr A[i] reprezentând volumul cutiei i = 1,2...,n. Aceste cutii trebuie transportate din localitatea A în localitatea B știind ca se pot efectua maxim k transporturi (în cazul în care s-ar efectua mai multe mașina ar rămâne fără combustibil) și de asemenea fiind o mașina închiriată trebuie sa aibă capacitatea minimă x necesară pentru a efectua cele k transporturi. Numărul x este cel ce îi dă bătăi de cap lui Alex așa ca el vă roagă să îl ajutați!

Date de intrare

Pe prima linie a fișierului profu.in se vor găsi cele doua numere n și k cu semnificația din enunț apoi pe a doua linie a fișierului se vor găsi n numere naturale.

Date de ieșire

Fișierul de ieșire profu.out va conține pe prima linie numărul x, reprezentând capacitatea minima a mașini ce trebuie închiriată.

Restricții și precizări

• 1 ≤ n ≤ 500.000
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000

Exemplu

profu.in

6 3
7 3 2 3 1 4

profu.out

8

Explicație

La primul transport este încărcată prima saltea (care are volumul 7). La cel de-al doilea transport sunt încărcate saltele 2 și 3 (volumul total este 3 + 2 = 5). La cel de-al treilea transport sunt încărcate saltele 4, 5 și 6 (volumul total este 3 + 1 + 4 = 8 fiind cel mai mic rezultat posibil)

#include <bits/stdc++.h>

using namespace std;
ifstream cin("profu.in");
ofstream cout("profu.out");
int a[500001] , k , n;

int poate(int a[] , int n , long long x , int k)
{
    long long s = 0;
    int c = 1;
    for(int i = 1 ; i <= n ; i++)
    {
        s += a[i];
        if(s > x)
        {
            c++;
            if(c > k) return 0;
            s = a[i];
        }
    }
    if(c <= k) return 1;
    else return 0;
}

long long cautarebinara(int a[] , int n , int max , long long x , int k)
{
    long long st = max , dr = x;
    while(st <= dr)
    {
        long long mij = (st+ dr) / 2;
        if(poate(a , n , mij , k)) dr = mij-1;
        else st = mij+1;
    }
    return st;
}
int main()
{
    long long x = 0;
    int max = 0;
    cin >> n >> k;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> a[i];
        x += a[i];
        if(a[i] > max) max = a[i];
    }
    cout << cautarebinara(a , n , max , x , k);
}