Problem:
You are given $n$ packages of $w_i$ kg from a belt conveyor in order ($i = 0, 1, ... n-1$). You should load all packages onto $k$ trucks which have the common maximum load $P$. Each truck can load consecutive packages (more than or equals to zero) from the belt conveyor unless the total weights of the packages in the sequence does not exceed the maximum load $P$. Write a program which reads $n$, $k$ and $w_i$, and reports the minimum value of the maximum load $P$ to load all packages from the belt conveyor. Input In the first line, two integers $n$ and $k$ are given separated by a space character. In the following $n$ lines, $w_i$ are given respectively. Output Print the minimum value of $P$ in a line. Constraints  $1 \leq n \leq 100,000$  $1 \leq k \leq 100,000$  $1 \leq w_i \leq 10,000$  Sample Input 1 5 3
8
1
7
3
9 Sample Output 1 10 If the first truck loads two packages of $\{8, 1\}$, the second truck loads two packages of $\{7, 3\}$ and the third truck loads a package of $\{9\}$, then the minimum value of the maximum load $P$ shall be 10. Sample Input 2 4 2
1
2
2
6 Sample Output 2 6 If the first truck loads three packages of $\{1, 2, 2\}$ and the second truck loads a package of $\{6\}$, then the minimum value of the maximum load $P$ shall be 6.

Solution (Python):

class Solve:
    def __init__(self):
        self.N, self.K = [int(i) for i in input().split()]
        self.W = [int(input()) for i in range(self.N)]

        self.a = max(self.W)-1  
        self.b = sum(self.W)  

    def check(self, P):
        k, p, W = 1, P, [w for w in self.W]
        for w in W:
            if p >= w:
                p -= w
            elif P >= w and k < self.K:
                k, p = k+1, P-w
            else:
                return False
        return True

    def solve(self):
        while self.b - self.a > 1:
            m = (self.a + self.b) // 2
            if self.check(m):
                self.b = m
            else:
                self.a = m
        return self.b

print(Solve().solve())

Solution (Python):
import sys

N, K = [int(s) for s in raw_input().split()]
ws = [int(raw_input()) for _ in xrange(N)]
lo, hi = max(ws), 100000 * 10000

while lo != hi:
    p = P = (lo + hi) / 2
    k = 1
    for w in ws:
        if w > p:
            p = P
            k += 1
        p -= w
    if k <= K:
        hi = P
    else:
        lo = P + 1

print lo

Solution (Python):
N, K = [int(s) for s in raw_input().split()]
ws = [int(raw_input()) for _ in xrange(N)]
lo, hi = max(ws) - 1, sum(ws)

while hi - lo > 1:
    p = P = (lo + hi) / 2
    k = 1
    for w in ws:
        if w > p:
            p = P
            k += 1
        p -= w
    if k <= K:
        hi = P
    else:
        lo = P

print hi

Solution (Python):


def check(P):
    i = 0
    for j in range(k):
        s = 0
        while s + w[i] <= P:
            s += w[i]
            i += 1
            if i == n:
                return n
    return i


def solve():
    left = 0
    right = sum(w) + 1 
    while right - left > 1:
        mid = (left + right) / 2
        v = check(mid)  
        if v >= n:
            right = mid
        else:
            left = mid
            
    return right

if __name__ == "__main__":
    n, k = map(int, input().split())
    w = [int(input()) for i in range(n)]
    print(int(solve()))

Solution (Python):
def check(P):
	global k, T, n

	i = 0
	for j in range(k):
		s = 0
		while s + T[i] <= P:
			s += T[i]
			i += 1
			if (i == n):
				return n
	
	return i

def solve():
	left = 0
	right = 100000 * 10000

	while right - left > 1:
		mid = (left + right) // 2
		v = check(mid)
		if (v >= n):
			right = mid
		else:
			left = mid

	return right

if __name__ == '__main__':
	n, k = map(int, input().split())
	T = [int(input()) for i in range(n)]

	ans = solve()
	print(ans)

Solution (Python):


def maxStack(k, p, W):
    nw = 0
    count = 0
    t = 1
    for x in W:
        if x > p:
            return count
        if nw + x <= p:
            nw += x
            count += 1
        else:
            if t == k:
                return count
            else:
                t += 1
                nw = x
                count += 1
    return count

n, k = map(int, raw_input().split())
W = [int(raw_input()) for i in range(n)]
left = 1
right = sum(W)
while left < right:
    mid = (left+right)/2
    v = maxStack(k, mid, W)
    if v >= n:
        right = mid
    else:
        left = mid+1
print left

Solution (Python):


def check(t, n, k, p):
    i = 0
    for j in range(k):
        s = 0
        while (s + t[i] <= p):
            s += t[i]
            i += 1
            if i == n:
                return n
    return i

if __name__ == "__main__":
    n, k = [int (x) for x in input().split()]
    t = []
    for i in range(n):
        t.append(int(input()))

    start, end = 0, 10000 * 100000

    while (end - start > 1):
        mid = (start + end) // 2
        v = check(t, n, k, mid)
        if v >= n:
            end = mid
        else:
            start = mid

    print(end)

Solution (Python):
def checkCapacity(W,k,P):
    ws = 0
    cnt = 1
    for wi in W:
        if wi > P: return False
        ws += wi
        if ws > P:
            cnt += 1
            ws = wi
        if cnt > k: return False
    return True

if __name__=='__main__':
    n,k = list(map(int, input().split()))
    W = list(map(int,[input() for _ in range(n)]))
    Pmax = sum(W)
    Pmin = 0
    while Pmin < Pmax:
        P = (Pmax + Pmin) // 2
        if checkCapacity(W,k,P):
            Pmax = P
        else:
            Pmin = P + 1
    print(Pmax)

Solution (Python):
def checkCapacity(W,k,P):
    ws = 0
    cnt = 1
    for wi in W:
        ws += wi
        if ws > P:
            cnt += 1
            ws = wi
        if cnt > k: return False
    return True

if __name__=='__main__':
    n,k = list(map(int, input().split()))
    W = list(map(int,[input() for _ in range(n)]))
    Pmax = sum(W)
    Pmin = max(W)
    while Pmin < Pmax:
        P = (Pmax + Pmin) // 2
        if checkCapacity(W,k,P):
            Pmax = P
        else:
            Pmin = P + 1
    print(Pmax)

Solution (Python):
'''
Search - Allocation
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_D

Algorythm
Referenced 

1. Decide the searching point -> (top of the range + bottom of the range) / 2
2. Check whether it is possible to load all of the luggage to the trugs
    in the weight limit of the searching point
3. If it is possible, then move the top to the searching point
   If it is impossible, then move the bottom to the searching point + 1
4. Continue 1~4 as long as the top is greater than bottom

Range
Serching the maximum loading capacity(MLC) number
 between the maximam weight item num and the total weight num

top: total weight num
.
.
. <- search the num point
.
.
bottom: maximam weight item num

Why?
A1. Why not "bot = sp" but "bot = sp + 1"?
Q1. for example
    top = 5
    bot = 3
    sp = (5 + 3) / 2 = 4
    ...
    bot = sp
    sp = (5 + 4) / 2 = 4
    ...
    bot = sp
    ...for inf

A2. Why the top is total weight and bot is max weight?
Q2. Sure it is ok "top = 99999999, bot = 0".
     But, MLC never pass the total weight
      and the limit never be lower than the max.
       So, it is the most effective range.
'''


n, k = map(int,raw_input().split())
w = []
for i in xrange(n):
    w.append(input())


top = sum(w) 
bot = max(w) 


while top > bot:
    sp = (top + bot) / 2 

    tk = 0 
    weight = 0 

    
    
    for tw in w:
        if weight + tw <= sp:
            weight += tw
        else:
            tk += 1
            if tk >= k:
                
                bot = sp + 1
                break
            weight = tw
    else:
        
        top = sp


print top

Solution (Python):
'''
Search - Allocation
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_D

Algorythm
Referenced 

1. Decide the searching point -> (top of the range + bottom of the range) / 2
2. Check whether it is possible to load all of the luggage to the trugs
    in the weight limit of the searching point
3. If it is possible, then move the top to the searching point
   If it is impossible, then move the bottom to the searching point + 1
4. Continue 1~4 as long as the top is greater than bottom

Range
Serching the maximum loading capacity(MLC) number
 between the maximam weight item num and the total weight num

top: total weight num
.
.
. <- search the num point
.
.
bottom: maximam weight item num

Why?
A1. Why not "bot = sp" but "bot = sp + 1"?
Q1. for example
    top = 5
    bot = 3
    sp = (5 + 3) / 2 = 4
    ...
    bot = sp
    sp = (5 + 4) / 2 = 4
    ...
    bot = sp
    ...for inf

A2. Why the top is total weight and bot is max weight?
Q2. Sure it is ok "top = 99999999, bot = 0".
     But, MLC never pass the total weight
      and the limit never be lower than the max.
       So, it is the most effective range.

Note
1. This program contains the idea below
    - Using "binary search" idea
    - The appropriate range
2. To be the python program more fast
    - Using int(raw_input()) instead of input()
    - To rewrite the processings for the function is more fast 
'''


n, k = map(int,raw_input().split())
w = []
for i in xrange(n):
    w.append(int(raw_input()))

def tempf(sp):
    tk = 0 
    weight = 0 

    
    
    for tw in w:
        if weight + tw <= sp:
            weight += tw
        else:
            tk += 1
            if tk >= k:
                
                return False
            weight = tw
    else:
        
        return True


top = sum(w) 
bot = max(w) 


while top > bot:
    sp = (top + bot) / 2 

    if tempf(sp):
        top = sp
    else:
        bot = sp + 1


print top

Solution (Python):
n, k = map(int, input().split())
w = [int(input()) for _ in range(n)]


def binarysearch(start, end):
    left = start
    right = end
    mid = 0

    while left < right:
        mid = (left + right)//2
        
        if simulate(mid, w, k):
            right = mid
            
        else:
            mid += 1
            left = mid
    return mid


def simulate(prb, wei, dai):
    cnt = 1
    tmp = 0
    for j in wei:
        tmp += j
        if tmp > prb:
            tmp = j
            cnt += 1
            if cnt > dai:
                return False
    return True

print(binarysearch(max(w), sum(w)))

Solution (Python):
def check(p):
    s = w[0]
    track = 1
    for i in range(1, n):
        if s + w[i] <= p:
            s += w[i]
        else:
            track += 1
            if track > k: return False
            s = w[i]
    return True

n, k = [int(i) for i in input().split()]
w = []
for i in range(n):
    w.append(int(input()))
L = max(w)
R = sum(w)

if check(L):
    print(L)
else:
    while L + 1 < R:
        M = (L + R) // 2
        if check(M):
            R = M
        else:
            L = M
    print(R)

Solution (Python):
def binarytruck(maxweight,truck,num):
    disp = 0
    for n in range(num):
        if maxweight - targ[n] - disp < 0:
            disp = targ[n]
            truck -= 1
        else:
            disp += targ[n]
    return truck > 0
num,truck = (int(n) for n in input().split(' '))
global targ
targ = []
for n in range(num):
    targ.append(int(input()))
best = max(targ) - 1
worst = sum(targ)
maxweight = (best + worst ) // 2
cnt = 0
while best != worst - 1:
    cnt += 1
    if binarytruck(maxweight,truck,num):
        worst = maxweight
        maxweight = (best + maxweight) // 2

    else:
        best = maxweight
        maxweight = (worst + maxweight) // 2
print(worst)

Solution (Python):
import sys
n, k = list(map(int, input().split()))

ws = list(map(int, sys.stdin.read().split()))

def check(A, n, k, mid):
    j = 0
    for i in range(k):
        p = mid
        s = 0
        while (s + A[j]) <= p:
            s += A[j]
            j += 1
            if ( j == n ):
                return n
    return j

def solve(A, n, k):
    h = 100000 * 10000
    l = 0
    while 1 < (h - l):
        mid = (h + l) // 2
        v = check(A, n, k, mid)
        if v < n:
            l = mid
        else:
            h = mid
    return h

print(solve(ws, n, k))

Solution (Python):
n,k = map(int, input().split())
w = [int(input()) for _ in range(n)]

def bs(left, right):
    mid = 0
    
    while left < right:
        mid = (left + right ) //2
        if check(mid, w, k):
            right = mid
        else:
            mid += 1
            left = mid
    return mid

def check(v, wgt, num):
    cnt = 1
    tmp = 0
    for j in wgt:
        tmp += j
        if tmp > v:
            tmp = j
            cnt += 1
            if cnt > num:
                return False
    return True
    
print(bs(max(w), sum(w)))

Solution (Python):

def Check(P,k,w):
    i=0
    for j in range(k):
        s=0
        while s+w[i]<=P:
            s+=w[i]
            i+=1
            if i==n:
                return n
    return i

def Allocation(n,k,w):
    left=0
    right=100000000000000
    while right-left > 1:
        mid=int((left+right)/2)
        v=Check(mid,k,w)
        if v>=n:
            right=mid
        else:
            left=mid
    print(right)
  
if __name__=="__main__":
    a=input()
    n=int(a.split(" ")[0])
    k=int(a.split(" ")[1])
    w=[]
    for i in range(n):
        w.append(int(input()))
    Allocation(n,k,w)

Solution (Python):

def Check(P,k,w):
    i=0
    for j in range(k):
        s=0
        while s+w[i]<=P:
            s+=w[i]
            i+=1
            if i==n:
                return n
    return i

def Allocation(n,k,w):
    left=0
    right=100000000000000
    while right-left > 1:
        mid=int((left+right)/2)
        v=Check(mid,k,w)
        if v>=n:
            right=mid
        else:
            left=mid
    print(right)
  
if __name__=="__main__":
    a=input()
    n=int(a.split(" ")[0])
    k=int(a.split(" ")[1])
    w=[]
    for i in range(n):
        w.append(int(input()))
    Allocation(n,k,w)

Solution (Python):



import sys


class Solution:
    def __init__(self):
        """
        init input array
        """
        self.__input = sys.stdin.readlines()

    @property
    def solution(self):
        product_num = int(self.__input[0].split()[0])
        truck_num = int(self.__input[0].split()[1])
        weight_list = list(map(int, self.__input[1:]))

        assert product_num == len(weight_list)

        
        left, right, mid = max(weight_list), sum(weight_list), 0
        while left < right:
            mid = (left + right) // 2
            
            if self.check(mid, weight_list, truck_num):
                right = mid
            else:
                mid += 1
                left = mid
        return str(mid)

    @staticmethod
    def check(max_load_cursor, weight_list, truck_num):
        track_count = 1
        current_load = 0
        for item_weight in weight_list:
            current_load += item_weight
            
            if current_load > max_load_cursor:
                current_load = item_weight
                track_count += 1
                if track_count > truck_num:
                    return False
        return True


if __name__ == '__main__':
    case = Solution()
    print(case.solution)

Solution (Python):



import sys


class Solution:
    def __init__(self):
        """
        init input array
        """
        self.__input = sys.stdin.readlines()

    @property
    def solution(self):
        product_num = int(self.__input[0].split()[0])
        truck_num = int(self.__input[0].split()[1])
        weight_list = list(map(int, self.__input[1:]))

        

        
        left, right, mid = max(weight_list), sum(weight_list), 0
        while left < right:
            mid = (left + right) // 2
            
            if self.check(max_load_cursor=mid, weight_list=weight_list, truck_num=truck_num):
                right = mid
            else:
                mid += 1
                left = mid
        return str(mid)

    @staticmethod
    def check(max_load_cursor, weight_list, truck_num):
        track_count = 1
        current_load = 0
        for item_weight in weight_list:
            current_load += item_weight
            
            if current_load > max_load_cursor:
                current_load = item_weight
                track_count += 1
                if track_count > truck_num:
                    return False
        return True


if __name__ == '__main__':
    case = Solution()
    print(case.solution)

Solution (Python):
def calc_k(p, ws):
    k = 1
    s = 0
    for w in ws:
        if w > p:
            return None
        elif s + w <= p:
            s += w
        else:
            k += 1
            s = w
    return k

def search_minimum_p(k, ws):
    """
    ?????????P????????????????????¢?´¢??????
    max(P) = max(wi) * max(n)
    ????????¨???????????????1??°?????¨????????????????????????
    min(P) = max(wi)
    ?°?????????¨??????????????????????????§????????????????????????????????????
    """
    lp = max(ws)
    rp = 10000 * 100000

    while lp <= rp:
        cp = (lp + rp) // 2
        k1 = calc_k(cp, ws)
        if k1 <= k:
            
            k2 = calc_k(cp - 1, ws)
            if k2 == None or k2 > k:
                
                return cp
            else:
                
                rp = cp - 1
        else:
            
            lp = cp + 1

    return None

n, k = map(int, input().split())
ws = []
for i in range(n):
    ws.append(int(input()))

print(search_minimum_p(k, ws))

Solution (Python):
n, k = map(int, input().split())
ww = [int(input()) for _ in range(n)]
def chk(p):
    c = 1
    s = 0
    for w in ww:
        if w > p:
            return False
        if s + w <= p:
            s += w
        else:
            c += 1
            s = w
        if c > k:
            return False
    return True
def search(l, r):
    if r - l < 10:
        for i in range(l, r):
            if chk(i):
                return i
    m = (l + r) // 2
    if chk(m):
        return search(l, m + 1)
    else:
        return search(m, r)
print(search(0, 2 ** 30))

Solution (Python):
n, k = map(int, input().split())
ww = [int(input()) for _ in range(n)]
def chk(p):
    c = 1
    s = 0
    for w in ww:
        if w > p:
            return False
        if s + w <= p:
            s += w
        else:
            c += 1
            s = w
        if c > k:
            return False
    return True
def search(l, r):
    if r - l < 10:
        for i in range(l, r):
            if chk(i):
                return i
    m = (l + r) // 2
    if chk(m):
        return search(l, m + 1)
    else:
        return search(m + 1, r)
print(search(0, 2 ** 30))

Solution (Python):



def cal(truck_num, cargos):
    p = 0
    
    for i in range(len(cargos) - truck_num + 1):
        if not i == 0 and p < sum(cargos[:i + 1]):
            continue
        if truck_num > 1:
            r = max(sum(cargos[:i + 1]), cal(truck_num - 1, cargos[i + 1:]))
            if i == 0:
                p = r
            elif p > r:
                p = r
        else:
            return sum(cargos)
    return p

def check(truck_num, carogs, target_load):
    
    cur_truck = 1
    cur_weight = 0
    for weight in cargos:
        cur_weight += weight
        if cur_weight > target_load:
            cur_weight = weight
            cur_truck += 1
            if cur_truck > truck_num:
                return False
    return True

def solve(truck_num, cargs):

    max_load = sum(cargos)
    min_load = max(cargos)
    
    while min_load < max_load:
        target_load = int((min_load + max_load)/2)
        if check(truck_num, cargos, target_load):
            max_load = target_load
        else:
            min_load = target_load + 1
        
        
    return max_load

if __name__ == "__main__":
    line = input()
    truck_num = int(line.split(" ")[1])
    line_num = int(line.split(" ")[0])
    cargos = [int(input()) for i in range(line_num)]
    print(solve(truck_num,cargos))

Solution (Python):


global N,K
global ws

def check(max_p):
    track=0
    now=0
    for i in range (N):
        if(ws[i]>max_p):return False
        if(now+ws[i]>max_p):
            track+=1
            now=ws[i]
        else:
            now+=ws[i]
    if now>0:
        track+=1
    if(track>K):
        return False
    else:
        return True

N,K=map(int,input().split())

ans=0
now=0
ws=[]
for i in range(N):
    w=int(input())
    ws.append(w)

amin=0
amax=int(1E20)

while amin+1!=amax:
    amid=(amin+amax)//2
    if(check(amid)):
        amax=amid
    else:
        amin=amid
print(amax)

Solution (Python):


global N,K
global ws

def check(max_p):
    track=0
    now=0
    for i in range (N):
        if(ws[i]>max_p):return False
        if(now+ws[i]>max_p):
            track+=1
            now=ws[i]
        else:
            now+=ws[i]
    if now>0:
        track+=1
    if(track>K):
        return False
    else:
        return True

N,K=map(int,input().split())

ans=0
now=0
ws=[]
for i in range(N):
    w=int(input())
    ws.append(w)

amin=0
amax=int(1E30)

while amin+1!=amax:
    amid=(amin+amax)//2
    if(check(amid)):
        amax=amid
    else:
        amin=amid
print(amax)

Solution (Python):


global N,K
global ws

def check(max_p):
    track=0
    now=0
    for i in range (N):
        if(ws[i]>max_p):return False
        if(now+ws[i]>max_p):
            track+=1
            now=ws[i]
        else:
            now+=ws[i]
    if now>0:
        track+=1
    if(track>K):
        return False
    else:
        return True

N,K=map(int,input().split())

ans=0
now=0
ws=[]
for i in range(N):
    w=int(input())
    ws.append(w)

amin=0
amax=int(1E48)

while amin+1!=amax:
    amid=(amin+amax)//2
    if(check(amid)):
        amax=amid
    else:
        amin=amid
print(amax)

Solution (Python):
def calc_allocatable_packet(packets, num_of_trucks, p_max):
    """ ?????????????????°?????????????????§?????????????±?????????????n??°??????????????????????????????????????°????±??????? """
    num_of_packets = len(packets)
    next_p = 0  
    for t in range(num_of_trucks):
        payload = 0  
        while next_p < num_of_packets:
            if payload + packets[next_p] <= p_max:  
                payload += packets[next_p]
                next_p += 1
            else:
                break  
    return next_p


def calc_minimum_payload(packets, num_of_trucks):
    num_of_packets = len(packets)
    lower_limit = packets[0]
    upper_limit = 10000 * num_of_packets

    while lower_limit < upper_limit:
        middle = (lower_limit + upper_limit) // 2
        result = calc_allocatable_packet(packets, num_of_trucks, middle)
        if result < num_of_packets:
            lower_limit = middle + 1
        else:
            upper_limit = middle

    return lower_limit


if __name__ == '__main__':
    
    num_of_packets, num_of_trucks = [int(x) for x in input().split(' ')]
    packets = [int(input()) for _ in range(num_of_packets)]
    
    
    
    
    
    
    
    



    
    result = calc_minimum_payload(packets, num_of_trucks)

    
    print(result)

Solution (Python):


n, k = map(int, input().rstrip().split())
w = [0 for _ in range(n)]
for i in range(n):
    w[i] = int(input())
    







count = 0

def check(P):
    m = 0
    ik = 1
    for i in range(n):
        global count
        count += 1
        new = m + w[i]
        if new > P:
            m = w[i]
            ik += 1
            if ik > k:
                return False
        else:
            m = new
    return True

s = max(sum(w)//k, max(w))
e = sum(w)

while True:
    P = (s + e)//2
    
    if s == e:
        break
    if check(P):
        e = P
    else:
        s = P + 1
            
        
print(P)

Solution (Python):
import sys

def check_sekisairyo(p_min):
    p_now = 0
    k_now = 0
    for w in w_i:
        p_now += w
        if p_now > p_min:
            p_now = w
            k_now += 1
        elif p_now == p_min:
            p_now = 0
            k_now += 1
        if k_now == k and p_now != 0:
            return False
    return True

n, k = map(int, input().split())
w_i = [int(input()) for i in range(n)]
left, right, p_min = max(w_i), sum(w_i), 0
while left < right:
    p_min = (left + right) // 2
    if check_sekisairyo(p_min):
        right = p_min
    else:
        left = p_min = p_min + 1
print(p_min)

Solution (Python):
import sys
import math

def is_capable(n, k, w, P):
    track = 0
    cnt = 0
    i = 0

    while cnt < k:
        if i == n:
            return True

        if track + w[i] > P:
            track = 0
            cnt += 1
        else:
            track += w[i]
            i += 1

    return False
    pass


n, k = map(int, sys.stdin.readline().split())
w = []
for i in range(n):
    w.append(int(sys.stdin.readline().strip()))

'''
print(n,k)
print(w)
'''



if k == 1:
    ans = sum(w)
    print(ans)
elif n == 1:
    ans = w[0]
    print(ans)
else:
    max_p = sum(w)
    min_p = math.ceil(max_p / k) - 1

    
    

    capable = {min_p:False, max_p:True}

    
    
    bottom = min_p
    top = max_p

    while bottom < top:
        mid = (bottom + top) // 2

        if mid not in capable:
            capable[mid] = is_capable(n, k, w, mid)

        if capable[mid] == True:
            if (mid - 1) not in capable:
                capable[mid - 1] = is_capable(n, k, w, mid - 1)

            if capable[mid - 1] == False:
                ans = mid
                break
            else:
                top = mid
        elif capable[mid] == False:
            if (mid + 1) not in capable:
                capable[mid + 1] = is_capable(n, k, w, mid + 1)

            if capable[mid + 1] == True:
                ans = mid + 1
                break
            else:
                bottom = mid + 1

    print(ans)

Solution (Python):
import sys
import math

def is_capable(n, k, w, P):
    track = 0
    cnt = 0
    i = 0

    while cnt < k:
        if i == n:
            return i

        if track + w[i] > P:
            track = 0
            cnt += 1
        else:
            track += w[i]
            i += 1

    return i
    pass


n, k = map(int, sys.stdin.readline().split())
w = []
for i in range(n):
    w.append(int(sys.stdin.readline().strip()))

'''
print(n,k)
print(w)
'''



if k == 1:
    ans = sum(w)
    print(ans)
elif n == 1:
    ans = w[0]
    print(ans)
else:
    max_p = sum(w)
    min_p = math.ceil(max_p / k) - 1

    
    
    
    bottom = min_p
    top = max_p

    while top - bottom > 1:
        mid = (bottom + top) // 2

        if is_capable(n, k, w, mid) == n:
            top = mid
        else:
            bottom = mid

    print(top)

Solution (Python):
def check(p, k, arr):
  subtotal = 0
  num_of_tracks = 1
  for a in arr:
    subtotal += a
    if subtotal > p:
      num_of_tracks += 1
      if num_of_tracks > k: return False
      subtotal = a
  return True

n, k = map(int, input().split())
arr = [int(input()) for i in range(n)]

min_p = max(arr)
max_p = sum(arr)
while min_p < max_p:
  mid_p = (min_p + max_p) // 2
  if check(mid_p, k, arr):
    max_p = mid_p
  else:
    min_p = mid_p + 1

print(min_p)

Solution (Python):
n,k = map(int, input().split())
w = [int(input()) for _ in range(n)]

def check(p):
    c = t = 0
    for wi in w:
        t += wi
        if t > p:
            t = wi
            c += 1
            if c >= k:
                return False
    return True

s = max(w)
l = sum(w)
m = l + (s-l)*k//n
while s < l:
    if check(m):
        l = m
    else:
        s = m+1
    m = (s+l)//2
print(m)

Solution (Python):
n,k = map(int, input().split())
w = [int(input()) for _ in range(n)]

def check(p):
    c = t = 0
    for wi in w:
        t += wi
        if t > p:
            t = wi
            c += 1
            if c >= k:
                return False
    return True

s = max(w)
l = sum(w)
while s < l:
    m = (s+l)//2
    if check(m):
        l = m
    else:
        s = m+1
print(s)

Solution (Python):
n,k = map(int, input().split())
w = [int(input()) for _ in range(n)]

def check(p):
    c = t = 0
    for wi in w:
        t += wi
        if t > p:
            t = wi
            c += 1
            if c >= k:
                return False
    return True

s = max(w)
l = sum(w)
while s != l:
    m = (s+l)//2
    if check(m):
        l = m
    else:
        s = m = m+1
print(s)

Solution (Python):
n,k = map(int, input().split())
w = [int(input()) for _ in range(n)]

def check(p):
    c = t = 0
    for wi in w:
        t += wi
        if t > p:
            t = wi
            c += 1
            if c >= k:
                return False
    return True

s = max(w)
l = sum(w)
while s < l:
    m = (s+l)//2
    if check(m):
        l = m
    else:
        s = m = m+1
print(s)

Solution (Python):
import sys
import math 

def be_able_to_convey(w, k, p):
	counter = 0
	cur_weight = 0
	for wi in w:
		if wi > p:
			return False

		cur_weight += wi
		if(cur_weight > p):
			cur_weight = wi
			counter += 1
			if(counter >= k):
				return False

	return True


fin = sys.stdin

n, k = map(int, fin.readline().split())
w = [0 for i in range(n)]

for i in range(n):
	w[i] = int(fin.readline())
	
pmin = 1
pmax = int(10e9)

while pmin < pmax:
	p = math.ceil((pmin + pmax) / 2)
	if p == pmin or p == pmax:
		if be_able_to_convey(w, k, pmin):
			p = pmin
		else:
			
			
			p = pmax
		break

	if not be_able_to_convey(w, k, p):
		pmin = p
	else:
		pmax = p

print(p)

Solution (Python):
import sys
n,k = map(int,input().split())
w = list(map(int,sys.stdin.readlines()))

def binarysearch(start,end):
    left = start
    right = end
    middle = 0
    while left < right:
        middle = (left + right)//2
        if simulate(middle,w,k):
            right = middle
        else:
            left = middle + 1
    return left

def simulate(prb,wei,dai):
    count = 1
    tmp = 0
    for j in wei:
        tmp += j
        if tmp > prb:
            tmp = j
            count += 1
            if count > dai:
                return False
    return True

print(binarysearch(max(w), sum(w)))

Solution (Python):
import sys

def binarySearch(t,w):
    left = max(w)
    right = sum(w)
    while left < right:
        middle = (left + right) // 2
        if hantei(t,w,middle):
            right = middle 
        else:
            left = middle + 1
    return left
            
def hantei(t,w,p):
    track_on = 0
    daisu = 1
    for j in range(len(w)):     
        track_on += w[j]
        if track_on > p:
            daisu += 1
            track_on = w[j]
            if daisu > t:
                return False
    return True


nimotsu, track = map(int,input().split())
weight = list(map(int,sys.stdin.readlines()))



print(binarySearch(track,weight))