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):
def ok(p,l,k):
    c=1
    c1=0
    for i in l:
        if i>p:
          return False
        elif c1+i>p:
            c+=1
            c1=i
        else:
            c1+=i
    if c>k:
        return False
    else:
        return True
def nibutan(list1,k,n):
    l=0
    h=n*10000
    while l+1<h:        
        m=int((l+h)/2)
        if ok(m,list1,k):
            h=m
        else:
            l=m
    return h
n,k=map(int,input().split())
l=[]
for i in range(n):
    l.append(int(input()))
print(nibutan(l,k,n))

Solution (Python):
n,t = map(int,input().split())
lug = [int(input()) for i in range(n)]
right = sum(lug)+1
left = max(lug)-1

def is_ok(lug,t,a):
    truck_num = 1
    truck = 0
    for i in lug:
        if i > a:
            return False
        truck += i
        if truck ==a:
            truck = 0
            truck_num += 1
        elif truck > a:
            truck = i
            truck_num += 1
    if truck == 0:
        truck_num -= 1
    if truck_num > t:
        return False
    return True

while left+1 < right:
    center = (left + right)//2
    if is_ok(lug,t,center):
        right = center
    else:
        left = center
print(right)

Solution (Python):
n, k = [int(i) for i in input().split()]
w = []
for ni in range(n):
    w.append(int(input()))

def countPackages(P):
    i = 0
    for ki in range(k):
        sum = 0
        while i < n and sum + w[i] <= P:
            sum += w[i]
            i += 1
    return i

P_min = 0
P_max = 100000 * 10000
while P_min < P_max:
    P = (P_max + P_min)//2
    if countPackages(P) < n:
        P_min = P + 1
    else:
        P_max = P
print(P_min)

Solution (Python):
import sys
input = sys.stdin.readline

max_n = 100000
max_k = 100000
max_w = 10000


def check(p):
  global N, K, T

  i = 0
  for k 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 = max_k * max_w

  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 _ in range(N)]

  ans = solve()
  print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

max_n = 100000
max_k = 100000
max_w = 10000


def check(p):
  global N, K, T

  i = 0
  for k 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 = max_k * max_w

  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 _ in range(N)]

  ans = solve()
  print(ans)

Solution (Python):
def trucks_needed(pack, p):
    count = 1
    sum = 0
    for i in pack:
        if i > p:
            return -1
        elif sum + i > p:
            count += 1
            sum = i
        else:
            sum += i
    return count

values = input().split(" ")
n = int(values[0])
k = int(values[1])
pack = []
for i in range(n):
    pack.append(int(input()))

sum = 0
max = 0
for i in pack:
    if i > max:
        max = i 
    sum += i
ave = int(sum / k)
if ave > max:
    start = ave
else:
    start = max

left = start
right = sum + 1

while left < right:
    mid = int((left + right) / 2)
    
    num = trucks_needed(pack, mid)
    
    if num <= k:
        right = mid
    else:
        left = mid + 1
print(right)

Solution (Python):
def solve():
    import sys
    n, k = map(int, input().split())
    ws = tuple(map(int, sys.stdin))

    ok, ng = sum(ws), max(ws)-1

    while ok-ng > 1:
        mid = (ok+ng+1)//2
        current = 0
        count = 0
        for w in ws:
            if current + w > mid:
                current = w
                count += 1
            else:
                current += w
        if count < k:
            ok = mid
        else:
            ng = mid

    print(ok)


if __name__ == "__main__":
    solve()

Solution (Python):
import sys


def check(p):
    tmp = 0
    cnt = 1
    flag = 0
    for w in w_list:
        if w > p:
            flag = -1
            break
        tmp += w
        if tmp > p:
            cnt += 1
            tmp = w
        if cnt > k:
            flag = -1
            break
    return flag


def solve():
    left = 0
    right = w_max
    while (right - left > 1):
        mid = int((left + right) / 2)
        flag = check(mid)
        if flag == 0:
            right = mid
        else:
            left = mid
    return right


input = sys.stdin.readline
n, k = map(int, input().split())
w_list = []
w_max = 0
for _ in range(n):
    w = int(input())
    w_max += w
    w_list.append(w)
print(solve())

Solution (Python):
def f(x:int)->bool:
    """return (積載量ｘ),k台でいけるか
    """
    global K, ws
    track_cnt = 1
    weight = 0
    for wi in ws:
        if wi > x: return False
        if weight+wi > x:
            track_cnt += 1
            weight = wi
        else:
            weight += wi
    return track_cnt <= K

def binary_search(f, s:int, t:int)->int:
    """f: function(x:int)->bool
    f(s)=False, f(t)=True，f は広義単調増加
    return : [s, t) での f(x)=True なる最小のx
    """
    ng = s-1
    ok = t
    while ok - ng > 1:
        mid = (ok + ng)//2
        if f(mid): ok = mid
        else:      ng = mid
        

    if ok==s-1:
        raise(ValueError("For all x, f(x)=False"))
    return ok

if __name__ == "__main__":
    N,K = map(int, input().split())
    ws = [int(input()) for _ in range(N)]
    MAX_P = 10**10
    MIN_P = 0
    print(binary_search(f, MIN_P, MAX_P))

Solution (Python):
n, loads = map(int,input().split(" "))
packages = []
for i in range(n):
    packages.append(int(input()))

def ifOK(p):
    j = 0
    sum = 0
    count = 0
    while j < n:
        if sum + packages[j] > p:
            count += 1
            sum = packages[j]
        else:
            sum += packages[j]
        j += 1
    if count <= loads-1:
        return True

left = max(packages)
right = sum(packages)

while True:
    mid = (left + right)//2
    if mid == max(packages):
        print(mid)
        break
    elif mid == sum(packages)-1:
        print(sum(packages))
        break
    if ifOK(mid):
        if not ifOK(mid-1):
            print(mid)
            break
        right = mid
    else:
        left = mid

Solution (Python):
def allocation(p, w, n, k):
    truck = [0]*k
    idx = 0
    cnt = 0
    for i in range(n):
        if (truck[idx] + w[i]) > p:
            idx += 1
            if idx >= k:
                break
        if w[i] > p:
            continue
        truck[idx] += w[i]
        cnt += 1
    return cnt
n, k = map(int,input().split())
w = [int(input()) for i in range(n)]
left = 0
right = 100000*10000
while left < right:
    mid = (left + right)//2
    ans1 = allocation(mid, w, n, k)
    ans2 = allocation(mid-1,w, n, k)
    if n == ans1 and ans2 < n:
        print(mid)
        break
    elif n == ans1:
        right = mid
    elif ans1 < n:
        left = mid

Solution (Python):
from math import ceil


def readIntLine(n: int):
  return [int(input()) for _ in range(n)]


n, k = [int(i) for i in input().split()]
ws = readIntLine(n)

def check(p):
    cnt = 0
    for _ in range(k):
        s = 0
        while s + ws[cnt] <= p:
            s += ws[cnt]
            cnt += 1
            if cnt == n:
                return cnt
    return cnt



left = 0
right = 100000 * 10000

while right - left > 1:
    mid = (left + right) // 2

    if check(mid) >= n:
        right = mid
    else:
        left = mid


print(right)

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


   
n,k = list(map(int, input().split(' ')))
weights = [None for _ in range(n)]
for i in range(n):
    weights[i] = int(input())
left = 0 
right = 100000 * 10000
while left + 1 < right:
    mid = left + (right-left)//2
    result = check(k,mid,n,weights)
    if result < n:
        left = mid
    else:
        right = mid
print(left + 1)

Solution (Python):
def track(P,w):
    ans = 1
    p = P
    for i in w:
        if i > P:
            return 0
        if p - i >= 0:
            p = p - i
        else:
            ans += 1
            p = P - i
    return ans


nk = list(map(int, input().split()))
n = nk[0]
k = nk[1]
w = []
for i in range(n):
    w.append(int(input()))
left = max(w)
right = sum(w) + 1
while left < right:
    mid = (left + right) // 2
    track_mid = track(mid, w)
    if track_mid <= k:
        right = mid
    else:
        left = mid + 1
print(left)

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


def loadnum(p):
    ni = 0
    for _ in range(k):
        s = 0
        while (s+w[ni]) <= p:
            s += w[ni]
            ni += 1
            if ni == n:
                return n
    return ni

    
lp, rp = 0, 10000*100000
while lp < rp:
    mp = (lp+rp)//2
    
    num = loadnum(mp)
    if num >= n:
        rp = mp
    else:
        lp = mp+1

print(lp)

Solution (Python):
N, K = map(int, input().split())
W = [int(input()) for _ in range(N)]
P_MIN = max(W)
P_MAX = 10 ** 9
while P_MIN < P_MAX:
    P = (P_MAX + P_MIN) // 2  
    M = 0
    i = 0
    while i < N:  
        mass = 0  
        while i < N and mass + W[i] <= P:  
            mass += W[i]
            i += 1
        M += 1  
    if M > K:  
        P_MIN = P + 1
    elif M <= K:  
        P_MAX = P
print(P_MIN)

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

def aa(m):
    g = c = 0 
    for i in w:
        g += i
        if g > m:
            c += 1
            g = i
            if c >= k:return 0
    return 1

l = max(w)
r = sum(w)

while l<r:
    m = (l+r)//2
    if aa(m):r = m
    else:l = m+1
print(r)

Solution (Python):
MAX_P = 100000 * 10000

n, k = map(int, input().split())
w = list()
for _ in range(n):
    w.append(int(input()))




def check(p):
    k_no = 1
    tmp = 0
    for i, wi in enumerate(w):
        if wi > p:
            return i
        if tmp + wi > p:
            if k_no == k:
                return i
            else:
                k_no += 1
                tmp = wi
        else:
            tmp += wi
    return len(w)


def solve():
    left = 1
    right = MAX_P

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

    
    
    if check(left) >= n:
        return left
    else:
        return right




print(solve())

Solution (Python):



def trackNum(P, wi, n):
    track = 1
    sum = 0
    if P < max(wi):
        return -1
    for i in range(n):
        sum += wi[i]
        if sum > P:
            track += 1
            sum = wi[i]
        elif sum == P and i < n - 1:
            track += 1
            sum = 0
    return track
    
n, k = map(int,input().rstrip().split())
wi = []
for i in range(n):
    wi.append(int(input().rstrip()))

start = max(wi)
end = sum(wi)
while start < end:
    half = int((start+end)/2)
    if trackNum(half, wi, n) > k:
        start = half
    else: 
        end = half
    if start + 1 == end:
        if trackNum(start, wi, n) <= k:
            end = start
        break

print(end)

Solution (Python):
import sys
input = sys.stdin.readline


def load_num_check(max_load, k, n, w):
    item_num = 0
    for _ in range(k):
        current_load = 0
        while True:
            weight = w[item_num]
            next_load = current_load + weight
            if (next_load > max_load):
                break
            item_num += 1
            if(item_num == n):
                return n
            else:
                current_load = next_load
    return item_num


def main():
    n, k =  map(int, input().split())
    w = [int(input()) for _ in range(n)]
    min_load = 0
    max_load = 1e4 * 1e5
    while(max_load - min_load > 1):
        mid_load = (max_load + min_load) // 2
        loadable_item_num = load_num_check(mid_load, k, n, w)
        if (loadable_item_num >= n):
            max_load = mid_load
        else:
            min_load = mid_load
        
    print(int(max_load))
        

if __name__ == "__main__":
    main()

Solution (Python):
from sys import stdin

def binSearch(k, p_min, p_max):
    global w
    while p_max-p_min > 1:
        mid = p_min + (p_max-p_min)//2
        if k >= countTrack(w, mid):
            p_max = mid
        else:
            p_min = mid

    return p_max

def countTrack(w, p):
    rest = []
    for wi in w:
        if len(rest) != 0 and rest[-1] >= wi:
            rest[-1] -= wi
        else:
            rest.append(p-wi)

    return len(rest)

n, k = [int(x) for x in stdin.readline().rstrip().split()]
w = [int(stdin.readline().rstrip()) for _ in range(n)]
print(binSearch(k, max(w)-1, 10000*100000+1))

Solution (Python):
import sys


def s():
    n, k = map(int, input().split())
    w = list(map(int, sys.stdin.readlines()))

    def f():
        c = t = 0
        for j in w:
            t += j
            if t > m:
                t = j
                c += 1
                if c >= k:
                    return 0
        return 1

    l, r = max(w), sum(w)
    while l < r:
        m = (l + r) // 2
        if f():
            r = m
        else:
            l = m + 1
    print(r)


if '__main__' == __name__:
    s()

Solution (Python):
import bisect


def main():
    n, k = map(lambda x: int(x), input().split())
    w = [int(input()) for _ in range(n)]

    cumulative_sum = [0]
    for weight in w:
        cumulative_sum.append(cumulative_sum[-1] + weight)
    p_min, p_max = max(w), cumulative_sum[-1]

    while p_min != p_max:
        p_mid = (p_min + p_max) // 2
        left_track = k
        index = 1
        while left_track > 0:
            left_track -= 1
            index = bisect.bisect_right(cumulative_sum, cumulative_sum[index-1] + p_mid)
            if index == len(cumulative_sum):
                break
        else:
            p_min = p_mid+1
            continue
        p_max = p_mid

    print(p_min)


if __name__ == '__main__':
    main()

Solution (Python):
def InputData():
    
    
    
    

    weight_len, track_num = [int(s) for s in input().split(" ")]
    weight_data = [int(input()) for _ in range(weight_len)]

    return weight_len, track_num, weight_data

def check(track_num, weight_len, weight_data, key):
    i = 0
    for j in range(track_num):
        s = 0
        while (s + weight_data[i]) <= key:
            s += weight_data[i]
            i += 1
            if i == weight_len:
                return weight_len

    return i

def binarySearch(right, weight_len, track_num, weight_data):

    left = 0

    while((right - left) > 1):
        mid = (left + right) // 2
        v = check(track_num, weight_len, weight_data, mid)
        if v >= weight_len:
            right = mid
        else:
            left = mid

    return right

def PrintOut(right):
    print(right)

def main():
    
    [weight_len, track_num, weight_data] = InputData()
    right = 100000 * 10000
    right = binarySearch(right, weight_len, track_num, weight_data)
    PrintOut(right)

if __name__ == '__main__':
    main()

Solution (Python):
N, K = list(map(int, input().split()))
table = [0]*N
max_W = 0
for i in range(N):
    table[i] = int(input())
    max_W = max(max_W, table[i])

left = max_W; right = 1000000000; mid = (left + right)//2;
ans = right

def is_ok(tmp_P):
    num_track = 1
    tmp_sum = 0
    for i in range(N):
        if tmp_sum + table[i] <= tmp_P:
            tmp_sum += table[i]
        else:
            num_track += 1
            tmp_sum = table[i]
            if num_track > K:
                return False
    return True

while left <= right:
    if is_ok(mid) == True:
        ans = mid
        right = mid - 1
    else:
        left = mid + 1
    mid = (left + right)//2;

print("%d"%(ans))

Solution (Python):


"""
二分探索の応用
"""

N, K = map(int, input().split())
aN = [int(input()) for i in range(N)]


def check(P):
    
    load = 0
    
    for j in range(K):
        truck = 0
        
        while truck + aN[load] <= P:
            truck += aN[load]
            load += 1
            
            if load == N:
                return N
    
    return load


hi = 10 ** 9
low = 0

while low+1 < hi:
    mid = (hi+low) // 2
    if check(mid) == N:
        hi = mid
    else:
        low = mid

print(hi)

Solution (Python):
import sys

n, k = map(int, sys.stdin.readline().split())
weights = [int(sys.stdin.readline()) for _ in range(n)]


def acceptable(p):
    rest = k
    capacity = p
    for w in weights:
        if w > capacity:
            rest -= 1
            if rest == 0:
                return False
            capacity = p - w
        else:
            capacity -= w
    return True


left = max(weights) - 1
right = sum(weights)

while left + 1 < right:
    mid = (left + right) // 2
    if acceptable(mid):
        right = mid
    else:
        left = mid

print(right)

Solution (Python):






import sys
input = sys.stdin.readline


def calc(l,k,m):
    n = len(l)
    kp = 1
    mp = 0
    for i in range(n):
        if (l[i] >  m ):
            return False
        if (mp + l[i] <= m ):
            mp += l[i]
            continue
        kp += 1
        mp = l[i]
    if (kp <= k):
        return True
    else:
        return False

def binSearch(l,k):
    left = 0
    right = 100000 * 100000
    mid = right // 2
    flg = False
    while right - left > 1:
        if calc(l,k,mid) == False:
            left = mid
            flg = True
        else:
            right = mid
            flg = False
        mid =  (right + left ) // 2 
    return right


def main():
    l = []
    (n,k) = map(int,input().split())
    for i in range(n):
        l.append(int(input()))
    t = binSearch(l,k)
    print (t)

if __name__ == '__main__':
   main()

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 judge(loads,truck,truck_weight):
    truck_num=1
    weight_sum=0
    for load in loads:
        if(weight_sum + load >truck_weight):
            truck_num+=1
            if(truck < truck_num):
                return 0
            weight_sum=load
        else:
            weight_sum+=load
    return 1




def binal_search(loads,truck,min,max):
    if(max ==min):
        return  min
    mid=(min+max)//2
    if(judge(loads,truck,mid)):
        return binal_search(loads,truck,min,mid)
    else:
        return binal_search(loads,truck,mid+1,max)


        


n,truck=map(int,input().split())
loads=[]
for loop in range(n):
    loads.append(int(input()))
loads_max=sum(loads)
loads_min=max(loads)
print(binal_search(loads,truck,loads_min,loads_max))

Solution (Python):
import math

def p(ws, k, pmin, pmax):
    if pmax - pmin <= 1:
        return pmax

    mid = pmin + math.ceil((pmax - pmin)/2)
    ts = []

    t = 0
    for w in ws:
        if mid < t+w:
            ts.append(t)
            t = 0

        t += w

    if t > 0:
        ts.append(t)

    if len(ts) <= k:
        return p(ws, k, pmin, mid)
    else:
        return p(ws, k, mid, pmax)

def main():
    n, k = [int(x) for x in input().split(' ')]

    pmin = 0
    sumW = 0
    ws = []

    for _ in range(n):
        w = int(input())
        ws.append(w)

        pmin = max(pmin, w)
        sumW += w

    print(p(ws, k, pmin-1, sumW))

if __name__ == '__main__':
    main()

Solution (Python):
import sys
n, k = map(int, sys.stdin.readline().split())

w = [int(sys.stdin.readline()) for _ in range(n)]
head = 0
tail = sum(w)
while head<tail-1:
    P = (head+tail)//2
    ld = 0 
    m = 1
    for u in w: 
        ld += u
        if ld>P: 
            m+=1 
            if k<m:    break 
            if u>P: break 
            ld = u
    else:
        tail=P
        continue
    head=P
    
print(tail)

Solution (Python):
'''
最大値 : n - k
最小値 : 1
8 1 7 3 9
興味あるのは最大値だけ。
'''

class Allocator(object):

    def __init__(self):
        self.N, self.K = map(int, input().split())
        self.ws = []

        for _ in range(self.N):
            self.ws.append(int(input()))

    def check(self, max_p):
        track, now = 0, 0
        for w in self.ws:
            if w > max_p:
                
                return False
            elif w + now > max_p:
                
                now = w
                track += 1
            else:
                
                now += w

        if now > 0:
            
            track += 1

        if int(self.K) < track :
            return False

        return True


amin, amax = 0, int(10E10)
allocate = Allocator()

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

print(amax)

Solution (Python):
import sys


sys.setrecursionlimit(1000000)


def li_input():
    return [int(_) for _ in input().split()]


def is_boardable(W, P, K):
    T = [0] * K

    wi = 0
    ti = 0
    while wi < len(W):
        if T[ti] + W[wi] <= P:
            T[ti] += W[wi]
            wi += 1
        else:
            ti += 1

            if ti == K:
                return False
    
    return True


def main():
    N, K = li_input()
    W = [int(input()) for _ in range(N)]

    l = 0
    r = 100000 * 10000

    while l + 1 < r:
        m = (l + r) // 2

        if is_boardable(W, m, K):
            P = m
            r = m
        else:
            l = m

    print(P)
    

main()

Solution (Python):
def allocation(A, k):
    def C(P):
        i = 0
        for j in range(k):
            s = 0  
            while s + A[i] <= P:
                s += A[i]
                i += 1
                if i == len(A): return True
        return False

    l = 0
    r = 100000*10000  
    while l !=r:
        mid = int((l + r) / 2)
        if C(mid):
            r = mid
        else:
            l = mid +1 
    return l

def main():
    N, k = (int(x) for x in input().split())
    A = [int(input()) for i in range(N)]
    print(allocation(A,k))


main()

Solution (Python):



from math import floor
from sys import stdin

def allocate(n, k, w, P):
    n_truck = 1
    load = 0
    for wt in w:
        
        if load + wt > P:
            n_truck += 1
            if n_truck > k:
                return False
            load = 0
        load += wt
    return True

def main():
    n, k = [int(x) for x in stdin.readline().split()]
    w = [int(x) for x in stdin]
    min_P = max(max(w), floor(sum(w) / k))
    max_P = sum(w)

    while min_P < max_P:
        mid_P = (min_P + max_P) // 2
        if allocate(n, k, w, mid_P):
            max_P = mid_P
        else:
            min_P = mid_P + 1
        
    
    print(min_P)

main()

Solution (Python):
def sum_of_list(A):
    sum = 0
    for i in A:
        sum += int(i)
    return sum

def load_number(A, p, k):
    capacity = p
    num = 0
    for i in A:
        if capacity < int(i):
            break
        elif p >= int(i) and k > 0:
            num += 1
            p -= int(i)
        elif p < int(i) and k > 1:
            num += 1
            k -= 1
            p = capacity
            p -= int(i)
        elif k == 0:
            break
    return num

def search_load_capacity(A, n, k):
    total_weight = sum_of_list(A)
    left = 0
    right = total_weight + 1
    while left < right:
        mid = int((left + right) / 2)
        if load_number(A, mid, k) >= n:
            if load_number(A, mid-1, k) < n:
                return mid
            else:
                right = mid
        else:
            left = mid + 1

n, k = (map(int,input().split()))
A = [input() for x in range(n)]
print(search_load_capacity(A, n, k))

Solution (Python):
import sys


f = sys.stdin
i, k = f.readline().split()
k = int(k)

arr = []

for line in f:
    arr.append(int(line.split()[0]))

def chkCanLoad(arr, k, P):
    tmpW = 0
    k -= 1

    for w in arr:
        tmpW += w
        if tmpW > P:
            k = k - 1
            if k < 0:
                return False
            else:
                tmpW = w
                if tmpW > P:
                    return False
    return True

P = 1
maxP = -1
minP = -10
cof = 2 
while maxP != minP + 1:
    chk = chkCanLoad(arr, k, P)  
    if chk:
        maxP = P
        newP = int(minP + (maxP - minP)/cof)
        P = newP
    else:
        minP = P
        if maxP < 0:
            P *= cof
        else:
            newP = int(minP + (maxP - minP)/cof)
            P = newP 

print(maxP)

Solution (Python):
def check(n, k, w, 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(n, k, w):
    left = 0
    right = n * max(w)
    while right - left > 1:
        mid = (left + right) // 2
        v = check(n, k, w, mid)
        if v >= n:
            right = mid
        else:
            left = mid

    return right


n, k = [int(i) for i in input().split()]
w = [int(input()) for i in range(n)]
print(solve(n, k, w))

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

left=max(tmp)-1
right=sum(tmp)
while left+1 < right:
	mid=(left+right)//2
	count=1
	now=0
	for i in tmp:
		if mid<now+i:
			now=i
			count+=1
		else:
			now+=i

	if count<=k:
		right=mid
	else:
		left=mid

print(right)

Solution (Python):

lines = '''\
5 3
8
1
7
3
9'''.split('\n')



def count(p,n,tracks,data):
  w = 0
  cnt = 0
  idx = 0
  while tracks > 0:
    if idx == n:
      break
    elif p >= data[idx] + w:
      w += data[idx]
      cnt += 1
      idx += 1
    else:
      tracks -= 1
      w = 0
  return cnt

n,tracks = [int(l) for l in input().split(' ')]
data = [int(input()) for i in range(n)]


wsum = 0
for dt in data:
  wsum += dt
wsum *= 2

def search(wsum,n,tracks,data):
  result = 0
  left = 0
  right = wsum
  while right - left > 1:
    mid = (left + right)//2
    v = count(mid,n,tracks,data)
    if v >= n:
      right = mid
    else:
      left = mid
  return right

r = search(wsum,n,tracks,data)
print(r)

Solution (Python):


def bs(n, k, W):
    left, right = max(W), sum(W)
    mid = 0
    while left < right:
        mid = left + (right - left) // 2
        if is_enough(mid, k, W):
            right = mid
        else:
            left = mid + 1
    return left

def is_enough(p, k, W):
    trk_cnt = 1
    weight = 0
    for i in W:
        weight += i
        if weight > p:
            trk_cnt += 1
            weight = i
            if trk_cnt > k:
                return False
    return True

def main():
    n, k = map(int, input().split())
    W = [int(input()) for _ in range(n)]
    rslt = bs(n, k, W)
    print(rslt)

if __name__ == '__main__':
    main()