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):
n = list(map(int, input().split()))
w = [0] * n[0]
for i in range(n[0]):
    w[i] = int(input())
    
def check(p):
    i = 0
    for j in range(n[1]):
        s = 0
        while s + w[i] <= p:
            s += w[i]
            i += 1
            if i == n[0]:
                return True
    return False

def solve():
    left = 0
    right = 100000 * 10000
    min_p = 100000 * 10000
    while right - left > 1:
        mid = (right + left) // 2
        if check(mid):
            if min_p > mid:
                min_p = mid
            right = mid
        else:
            left = mid
    print(min_p)

solve()

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

def track_num(n):
    cnt,track=0,1
    for i in A:
        if cnt+i>n:
            track +=1
            cnt=i
        else:
            cnt +=i
    return track

def Binaryserch():
    left,right=max(A),sum(A)+1
    ans=0
    while left<right:
        mid=(left+right)//2
        track=track_num(mid)
        if track<=k:
            ans=mid
            right=mid
        elif track>k:
            left=mid+1
    return ans

print(Binaryserch())

Solution (Python):
def track(A, n, k, P): 
	i = 0
	for _ in range(k):
		weight_of_track_j = 0
		while weight_of_track_j + A[i] <= P:
			weight_of_track_j += A[i]
			i += 1
			if i == n:
				return n
	return i


if __name__ == "__main__":
	n, k = map(int, input().split())
	w = []
	for _ in range(n):
		w.append(int(input()))
	left = 0
	right = 100000 * 10000 
	key = n
	while right - left > 1:
		mid = (left + right) // 2
		if key > track(w, n, k, mid):
			left = mid
		else:
			right = mid
	print(right)

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


def main():
    n, k = map(int, input().split())

    products = [int(input()) for _ in range(n)]

    left = 1
    right = 10000 * 100000  

    while left < right:
        mid = (left + right) // 2
        
        
        

        v = allocate(mid, k, products)
        

        if n <= v:
            right = mid
        else:
            left = mid + 1

    print(right)


def allocate(capacity, truckNum, products):
    
    v = 0
    tmp = 0
    truckNum -= 1
    while len(products) > v:
        product = products[v]

        
        

        if product > capacity:
            
            
            return 0

        if tmp + product <= capacity:
            
            tmp += product
        else:
            
            if truckNum > 0:
                
                truckNum -= 1
                tmp = product
            else:
                return v

        v += 1

    return v


if __name__ == '__main__':
    main()

Solution (Python):









def n_nimotu_if_P(P, k, arr):  
    weight = 0
    n_trucks = 1  
    for i, a in enumerate(arr):
        
        if P < a:  
            return i  

        if weight + a <= P:  
            weight += a
        else:
            n_trucks += 1  
            weight = a  

        if n_trucks == k+1:  
            return i  

    
    return len(arr)  



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





left, right = 0, 10000 * n
i_break = 0
while right - left > 1:
    mid = (left+right)//2
    if n <= n_nimotu_if_P(mid, k, luggages):  
        right = mid  
    else:  
        left = mid

print(right)

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

P = 10 ** 4 * 10 ** 5

mi = 0
ma = P

while ma - mi > 1:
    ans = (ma + mi) // 2
    now = 0
    count = 1
    is_success = True
    for v in w:
        if now + v <= ans:
            now += v
        else:
            now = v
            count += 1
            if count > k or now > ans:
                mi = ans
                is_success = False
                break
    if is_success:
        ma = ans

print(ma)

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



def main():
    N,K = map(int,input().split())
    W = []
    for _ in range(N):
        W.append(int(input()))

    
    lb = max(W)-1   
    ub = sum(W)     

    while ub - lb > 1:
        p = (lb + ub)//2

        v = 0
        k = 1
        for w in W:
            if v + w <= p: 
                v += w
            else:
                k += 1
                v = w

        if k <= K:
            
            ub = p
        else:
            
            lb = p


    
    print(ub)

if __name__ == '__main__':
    main()

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

W = []
for _ in range(n):
    w = int(input())
    W.append(w)
    
Baggages = W[:]
        
def _check(tmp_P):
    num_track = 1
    tmp_sum = 0
    for b in Baggages:
        if tmp_sum+b <= tmp_P:
            tmp_sum += b
        else:
            num_track += 1
            tmp_sum = b
            if num_track > k:
                return False
    return True
    

def check(P):
    i = 0
    for _ in range(k):
        s = 0
        while s+Baggages[i] <= P:
            s += Baggages[i]
            i += 1
            if i >= n:
                return True
    if i == n:
        return True
    else:
        return False

    
def binary_search(max_r):
    left = 0
    right = max_r
    
    while right-left > 1:
        mid = (left+right)//2
        if check(mid) == True:
            right = mid
        else:
            left = mid
    return right
            
max_p = sum(Baggages)+1
ans = binary_search(max_p)
print(ans)

Solution (Python):

def check(k, w, p):  
    j = 0
    for i in range(k):
        sum = 0
        while sum < p:
            if sum + w[j] > p:
                break
            else:
                sum += w[j]
                j += 1
            if j == len(w):  
                break
        if j == len(w):
            break

    if j == len(w):
        return True
    else:
        return False


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

left = sum(w) // k - 1
right = left + max(w)

while True:
    mid = (left + right) // 2
    

    if check(k, w, mid):
        right = mid
    else:
        left = mid
    if right - left <= 1:
        break
    

print(right)

Solution (Python):
def check(p):
    i = 0
    for j in range(track):
        s = 0
        while s + A[i] <= p:
            s += A[i]
            i += 1
            if i == budget:
                return True
    return False
    
def solve():
    left = max(A)
    right = sum(A)
    while (right - left > 1):
        mid = int((left + right) / 2)
        if check(mid):
            right = mid
        else :
            left = mid
    if check(left):
        return left
    else :
        return right

if __name__ == '__main__':
    budget, track = list(map(int, input().split()))
    A = []
    for n in range(budget):
        A.append(int(input()))     
    ans = solve()
    print(ans)

Solution (Python):
def ok(a, n, k, p):
    t = 0
    t_cnt = 0
    for w in a:
        if p < w:
            return -1
        if t + w > p:
            t_cnt += 1
            if t_cnt >= k:
                return -1
            t = w
        else:
            t += w
    return 0


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

P_max = n * 10000 // k + 10001

l = 0
r = P_max
m = 0
while l < r - 1:
    m = (l + r) // 2
    if ok(a, n, k, m) == 0:
        r = m
    else:
        l = m

print(r)

Solution (Python):
def check(P):
    global w, k
    t=1
    wt=0
    for wi in w:
        if wt+wi>P:
            wt=wi
            t+=1
        else:
            wt+=wi
        if t>k:
            return False
    return True

def search(l, r):
    if r-l==1:
        return r
    else:
        m=(l+r)//2
        if not check(m):
            return search(m,r)
        else:
            return search(l,m)

n,k=map(int,input().split())
w=[]
for i in range(n):
    w.append(int(input()))
S=sum(w);M=max(w)

P0=M-1


print(search(M-1,S))

Solution (Python):
import sys
n,k = map(int,input().split())
input = sys.stdin.readline
W = [int(input()) for i in range(n)]
l = max(W)-1
W.append(10**13)
h = sum(W)
while l+1 < h:
    ok = (l+h)//2
    track = 0
    cur = 0
    for i in range(n+1):
        cur += W[i]
        if cur > ok:
            track += 1
            cur = W[i]
        elif cur == ok:
            if i != n-1:
                track += 1
                cur = 0
    if track > k:
        l = ok
    else:
        h = ok
print(h)

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

left = max(W)
ans = right = 100000 * 100000


def is_ok(P):
    truck = 1
    t_sum = 0
    for i in range(n):
        if t_sum + W[i] <= P:
            t_sum += W[i]
        else:
            truck += 1
            t_sum = W[i]
            if truck > k:
                return False
    return True


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

print(ans)

Solution (Python):
import sys

def value(w,n,P):

	tmp_w = 0
	k = 1

	for i in range(n):
		if tmp_w + w[i] <= P:
			tmp_w += w[i]
		else:
			tmp_w = w[i]
			k += 1
	return k


def test():

	inputs = list(map(int,sys.stdin.readline().split()))
	n = inputs[0]
	k = inputs[1]
	w = []

	max = 0
	sum = 0

	for i in range(n):

		w.append(int(sys.stdin.readline()))

		if w[i] > max:
			max = w[i]

		sum += w[i]

	while max != sum:

		mid = (max + sum) // 2

		if value(w,n,mid) > k:
			max = mid + 1
		else:
			sum = mid


	print(max)

if __name__ == "__main__":
	test()

Solution (Python):
def check(k, W, p):
    s = 0
    count = 1
    for w in W:
        if s + w > p:
            count += 1
            s = 0
        s += w
    return count <= k

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

right = sum(W)
left = max(right // k, max(W)) - 1
while right - left > 1:
    p = (left + right) // 2
    if check(k, W, p):
        right = p
    else:
        left = p
print(right)

Solution (Python):
n,k=map(int, input().split( ))
w = []
for _ in range(n):
    w.append(int(input()))
mx=sum(w)
mn=max(w)
mid = (mx+mn)//2
w.append(1000000000000000)

while mn < mid:
    cnt = 1
    sm = 0
    for i in range(n):
        if sm <= mid-w[i]:
            sm +=  w[i]
        else:
            cnt+=1
            sm = w[i]

    if cnt>k:
        mn = mid
        mid = (mid+mx)//2
    else:
        mx = mid
        mid = (mid+mn)//2

ans=[]
for a in [mn,mid,mx]:
    cnt = 1
    sm = 0
    for i in range(n):
        if sm <= a - w[i]:
            sm +=  w[i]
        else:
            cnt+=1
            sm = w[i]

    if cnt<=k:
        ans.append(a)
    else:
        pass

print(min(ans))

Solution (Python):
def stackable(pack, tmp_p, k):
  cur_w = 0
  trucks = 1
  for i in range(len(pack)):
    if tmp_p < pack[i]:
      return False

    if cur_w + pack[i] <= tmp_p:
      cur_w += pack[i]
    else:
      cur_w = pack[i]
      trucks += 1

      if k < trucks:
        return False

  return True

n, k = map(int, input().split())
pack = []

for i in range(n):
  pack.append(int(input()))

left = int(sum(pack) / k)
right = max(pack) * n

while left < right - 1:
  tmp_p = int((left + right) / 2)
  if stackable(pack, tmp_p, k):
    right = tmp_p
  else:
    left = tmp_p

if stackable(pack, left, k):
  print(left)
else:
  print(right)

Solution (Python):
import sys
input = lambda: sys.stdin.readline()[:-1]
n,k=map(int,input().split())
w = [int(input()) for i in range(n)][::-1]
def maxnumber(p): 
	wc=w.copy()
	for i in range(k):
		lim=p
		while len(wc):
			if wc[-1]<=lim:
				lim-=wc.pop()
			else:break
	return len(wc)

minp=float('inf')
left,right=1,10**9+1
while left<right:
	mid=(left+right)//2
	maxn=maxnumber(mid)
	if maxn>0:
		left=mid+1
	else:
		right=mid
		minp=min(mid,minp)
print(minp)

Solution (Python):
import math

tr = []

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

def solve(n, k):
    left = 0
    right = 100000 * 100000
    while right - left > 1:
        mid = math.floor((left+right) / 2)
        v = check(n, k, mid)
        if v >= n:
            right = mid
        else:
            left = mid
    return right

def main():
    input_line = input().split(" ")
    n = int(input_line[0])
    k = int(input_line[1])
    
    for _ in range(n):
        w = int(input())
        tr.append(w)

    ans = solve(n, k)
    
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
N,K = map(int, raw_input().split())
W = [int(raw_input()) for _ in range(N)]

if N == 1:
    print W[0]
    exit()

def check(p):
    k = 1
    wt = 0
    for w in W:
        
        if wt + w <= mid:
            wt += w
        else:
            if w <= mid:
                wt = w
                k += 1
            else:
                
                return False
    
    return k <= K

left = min(W)
right = sum(W)
mid = 0
while left < right:
    
    mid = int((left + right) / 2)
    
    if check(mid):
        right = mid
    else:
        left = mid + 1

print left

Solution (Python):
def check_load(k, w, max_weight) -> bool:
  truck_itr = 0
  truck_weight = 0
  for w_i in w:
    if w_i > max_weight:
      return False
    if truck_weight + w_i > max_weight:
      truck_weight = 0
      truck_itr += 1

    truck_weight += w_i
    if truck_itr > k-1:
      return False
    
  return True

def solve():
  
  n,k = map(int, input().split())
  w = []
  truck = []
  for i in range(1,n+1):
    w.append(int(input()))

  
  right = sum(w) 
  left = sum(w)//n 
  max_weight = left
  while right-left > 1:
    
    if check_load(k, w, max_weight):
      right = max_weight
    else:
      left = max_weight

    max_weight = (right+left)//2
  
  print(right)
  
solve()

Solution (Python):
def check(p):
    global k, wlist   
    loadage = 0
    num = 1
    
    for w in wlist:
        loadage += w
        if loadage > p:
            num += 1
            if num > k:
                return False
            loadage = w
    return True

n, k = map(int, input().split())
wlist = []

for _ in range(n):
    wlist.append(int(input()))
    
maxw = max(wlist)
sumw = sum(wlist)
p = 0

while maxw < sumw:
    p = (maxw + sumw) // 2
    if check(p):
        sumw = p
    else:
        maxw = p = p+1
        
print(p)

Solution (Python):
def check_p(packages, n, trucks, max_p):
    i = 0
    for _ in range(trucks):
        sum = 0
        while sum + packages[i] <= max_p:
            sum += packages[i]
            i += 1
            if i == n:
                return i
    return i

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

left = 0
right = 10 ** 5 * 10 ** 4
while left + 1 < right:
    mid = (left + right) // 2
    num = check_p(packages, n, k, mid)
    if num < n:
        left = mid
    else:
        right = mid
print(right)

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):
n,t=[int(x) for x in input().split()]
w=[]
for i in range(n):
    w.append(int(input()))
 
totalw=sum(w)  
pmax=totalw
pmin=int(totalw/t)-1
 
def check(ptest):
    tk=1
    p=0
    global t
    global w
    global n
    i=0
     
    while i<n:
        p+=w[i]
        if p<=ptest:
            i+=1
        else:
            tk+=1
            p=0
             
        if tk>t:
            return 0
            
     
    return 1
     
         
while (pmax-pmin)>1:
    pmid=(pmax+pmin)//2
    if check(pmid)==1:
        pmax=pmid
    else:
        pmin=pmid
         
print(pmax)

Solution (Python):
from collections import deque
from enum import Enum
import sys
import math
 
BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001
 
 
N,K = 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 = 10000*100000;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):
def ok(m):
    c = 1
    tmp = m
    for w in W:
        if tmp > w:
            tmp -= w
        else:
            c += 1
            tmp = m - w
    return k >= c
 
n, k = map(int, input().split())
W = [int(input()) for i in range(n)]
 
left = max(W)
right = sum(W)+1
while left+1 < right:
    mid = (left+right) // 2
    if ok(mid):
        right = mid
    else:
        left = mid
print(left)

Solution (Python):
W_MAX = 10000
K_MAX = 100000


def main():
    n, k = map(int, input().split(' '))
    ws = [int(input()) for _ in range(n)]
    start = 1
    end = n*K_MAX
    target = int((start + end) / 2)
    while end > start:
        if number(target, ws) <= k:
                end = target
        elif number(target, ws) > k:
            start = target + 1
        target = int((start + end) / 2)
    print(target)


def number(p, ws):
    _p = p
    num_track = 1
    for w in ws:
        if w > p:
            return K_MAX+1
        if w > _p:
            _p = p
            num_track += 1
        if w <= _p:
            _p -= w
    return num_track


if __name__ == '__main__':
    main()

Solution (Python):
from typing import List


def is_able_to_load(tmp_P: int, weights: List[int], track_num_max: int) -> bool:
    track_num = 1
    tmp_sum = 0
    for w in weights:
        if tmp_sum + w <= tmp_P:
            tmp_sum += w
        else:
            track_num += 1
            tmp_sum = w
            if track_num > track_num_max:
                return False
    return True


if __name__ == "__main__":
    n, k = map(lambda x: int(x), input().split())
    weights = list(map(lambda x: int(input()), range(n)))

    left_weight = max(weights)
    right_weight = 10000 * 100000
    mid_weight = (left_weight + right_weight) // 2
    optimal_P = right_weight

    while left_weight <= right_weight:
        if is_able_to_load(mid_weight, weights, k):
            optimal_P = mid_weight
            right_weight = mid_weight - 1
        else:
            left_weight = mid_weight + 1

        mid_weight = (left_weight + right_weight) // 2

    print(f"{optimal_P}")

Solution (Python):
if __name__ == '__main__':
    n, k = map(int, input().split())
    total = 0
    data = []
    
    for i in range(n):
        data.append(int(input()))
        total += data[i]

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

    def solve():
        left = 0
        right = total + 1
        
        while right > left:
            mid = (right + left)//2
            c = check(mid) 
            if c >= n:
                right = mid
            else:
                left = mid + 1
        return right

    print(solve())

Solution (Python):
n,k = map(int,input().split())
w = []
for i in range(n):
	w.append(int(input()))
s = sum(w)
m = max(w) - 1
while (s-m) > 1:
	mid = (s+m+1)//2
	tmp = 0
	c = 0	
	for i in w:
		if tmp+i > mid:
			tmp = i
			c += 1
		else:
			tmp += i
	if c < k:
		s = mid
	else:
		m = mid
print(s)

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):
from sys import stdin
N, K = [int(_) for _ in stdin.readline().rstrip().split()]
W = [int(stdin.readline().rstrip()) for _ in range(N)]

def check(P):
    i = 0
    for _ in range(K):
        s = 0
        while s+W[i] <= P:
            s += W[i]
            i += 1
            if i == N:
                return N
    return i

def solver():
    mid, l, u = 0, 0, 100000*10000
    while u-l > 1:
        mid = (l+u)//2
        v = check(mid)
        if v >= N:
            u = mid
        else:
            l = mid
    return u
    
print(solver())

Solution (Python):

def f(w, n, k, v):
    
    i = 0
    space = 0
    while i < n:
        if space >= w[i]:
            space -= w[i]
            i += 1
        else:
            
            if k == 0:
                break
            k -= 1
            space = v
    return i


if __name__ == '__main__':
    n, k = map(int, raw_input().split())
    w = []
    maxv = -1
    for i in range(n):
        x = int(raw_input())
        w.append(x)
        maxv = max(maxv, x)

    left = 0
    right = n * maxv

    
    
    
    
    while right - left > 1:
        mid = (left + right) / 2
        v = f(w, n, k, mid)
        if v >= n:
            
            
            right = mid
        else:
            
            left = mid
    print right

Solution (Python):
from enum import Enum
from queue import Queue
import collections

import sys
import math

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

global n,k
global ws

def iSok(Pmax):
    truck = 0
    now = 0
    for i in range(n):
        if ws[i]>Pmax:
            return False
        if now+ws[i]>Pmax:
            truck += 1
            now = ws[i]
        else:
            now += ws[i]
    if now > 0:
        truck += 1
    if truck > k:
        return False
    else:
        return True

n,k = map(int,input().split())

now = 0
ws = [int(input()) for i in range(n)]
amin = 0
amax = sum(ws)

while amax-amin >1:
    amid = (amin + amax)//2
    if iSok(amid):
        amax = amid
    else:
        amin = amid
print(amax)

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

def check(p):
    i = 0
    for _ in range(k):
        wight = 0
        while wight+w[i] <= p:
            wight += w[i]
            i += 1
            if i == n:
                return n
    return i

if __name__ == '__main__':
    left = 0
    right = 100000 * 10000
    mid = 0
    while right - left > 1:
        mid = (left+right)//2
        v = check(mid)
        if v >= n:
            right = mid
        else:
            left = mid
    print(right)

Solution (Python):
class Check():
    def __init__(self, N, number_of_truck,baggage):
        self.N = N
        self.number_of_truck = number_of_truck
        self.baggage = baggage

    def check(self, mid):
        baggage_num = 0
        for j in range(self.number_of_truck):
            baggage_sum = 0
            while(baggage_sum + self.baggage[baggage_num] <= mid):
                baggage_sum += self.baggage[baggage_num]
                baggage_num += 1
                if baggage_num == self.N:
                    return baggage_num
        return baggage_num

    def binary_search(self):
        left = 0
        right = 1000000000
        while(left + 1 < right):
            mid = int((left + right) / 2)
            ok = self.check(mid)
            if ok == self.N:
                right = mid
            else :
                left = mid
        return right

def main():
    N,number_of_truck = [int(i) for i in input().split()]
    baggage = list()
    for i in range(N):
        i = int(input())
        baggage.append(i)
    ok = Check(N,number_of_truck,baggage)
    print(ok.binary_search())

if __name__ == "__main__":
    main()

Solution (Python):
def f(p, k, W):
    i = 0
    t = 0
    s = 0
    while i < len(W) and t < k:
        if s + W[i] <= p:
            s += W[i]
            i += 1
        else:
            s = 0
            t += 1
    return i


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

l = 0
r = 100000 * 10000 // k
while r - l > 1:
    mid = (l + r) // 2
    v = f(mid, k, W)
    if v >= n:
        r = mid
    else:
        l = mid

print(r)

Solution (Python):
n, k = map(int, input().split())
ws = []

def check(limit):
    idx_k = 0
    idx_n = 0
    temp = 0
    array = list(ws)

    while True:
        if idx_k == k or idx_n == n:
            break
        if temp + array[idx_n] <= limit:
            temp = temp + array[idx_n]
            idx_n += 1
        else:
            temp = 0
            idx_k += 1
    if idx_n < n:
        return False
    else:
        return True

for i in range(n):
    ws.append(int(input()))

limit = 1
left = 1
right = 100000 * 10000
mid = int((left + right) / 2)
ans = right

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

print(ans)

Solution (Python):
def main():
    n, k = map(int, input().split())
    w = []
    for i in range(n):
        w.append(int(input()))
    minp = max(w)
    maxp = sum(w)
    p = (minp + maxp) // 2
    while minp < maxp:
        l = w[0]
        t = 1
        for ww in w[1:]:
            if l + ww <= p:
                l += ww
            else:
                t += 1
                l = ww
        if t > k:
            minp = p + 1
        else:
            maxp = p
        p = (minp + maxp) // 2
    print(p)


if __name__ == '__main__':
    main()

Solution (Python):
import math



n, k = map(int, input().split())

W = []

for _ in range(n):
    W.append(int(input()))



P_min = max(max(W), math.ceil(sum(W) / k))
P_max = sum(W)



while P_min < P_max:
    P_mid = (P_min + P_max) // 2

    cnt_track = 1
    sum_load = 0
    flag_success = True

    for w in W:
        sum_load += w
        if sum_load > P_mid:
            sum_load = w
            cnt_track += 1

        if cnt_track > k:
            flag_success = False
            break

    if flag_success:
        P_max = P_mid
    else:
        P_min = P_mid + 1



print(P_min)

Solution (Python):
def check(p):
    curw = 0
    trucknum = k
    can = True
    for i in range(n):
        w = package[i]
        if w > p:
            can = False
            break
        if curw+w <= p:
            curw += w
        elif curw+w > p:
            trucknum -= 1
            curw = w
        if i == n-1 and curw > 0:
            trucknum -= 1
        if trucknum < 0:
            can = False
            break
    return can

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

M = sum(package)
m = 0
while True:
    if m+1 == M:
        break
    mid = (m+M)//2
    if check(mid):
        M = mid
    else:
        m = mid
print(M)

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

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

while left + 1 < right:
        mid = (left + right) // 2
        cnt = 1
        cur = 0
        for w in W:
                if mid < cur + w:
                        cur = w
                        cnt += 1
                else:
                        cur += w
        if cnt <= k:
                right = mid
        else:
                left = mid
print(right)

Solution (Python):


def check(P, k, w): 
    i = 0 
    n = len(w) 
    for _ 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 = int((left + right)/2)
        v = check(mid, k, w)
        if v>=n:
            right = mid
        else:
            left = mid
    return right

def main():
    n, k = map(int, input().split())
    w = [int(input()) for i in range(n)]
    answer = solve(n, k, w)
    print(answer)

main()

Solution (Python):
N, K = map(int, input().split())
W = [int(input()) for i in range(N)]


def can_be_loaded(P):
    """
    最大積載量がPのとき、何個の荷物が積めるかを返す
    """
    j = 0
    for i in range(K):
        s = 0
        while s + W[j] <= P:
            s += W[j]
            j += 1
            if j == N:
                return N
    return j


left = 0
right = 10**5 * 10**4  
while right - left > 1:
    mid = (left + right) / 2
    v = can_be_loaded(mid)  
    if v >= N:  
        right = mid
    else:
        left = mid
print(int(right))

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

def ok(p):
    t=1
    c=p
    for w in W:
        if w>p: return False
        if w<=c: c-=w
        else:
            t+=1
            c=p-w
            if t>k: return False
    return True
  
L=0
U=sum(W)
while U-L>1:
    x=(U+L)//2
    if ok(x): U=x
    else: L=x
print(U)

Solution (Python):
N, K = map(int, input().split())
W = [int(input()) for _ in range(N)]


def check(p):
    n = 0
    for i in range(K):
        s = 0
        while s + W[n] <= p:
            s += W[n]
            n += 1
            if n == N:
                return True
    return False


left = 0
right = 100000 * 100000
while right - left > 1:
    mid = (left + right) // 2
    if check(mid):
        right = mid
    else:
        left = mid
print(right)

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

totalw=sum(w)  
pmax=totalw
pmin=int(totalw/t)-1

def check(ptest):
    tk=1
    p=0
    global t
    global w
    global n
    i=0
    
    while i<n:
        p+=w[i]
        if p<=ptest:
            i+=1
        else:
            tk+=1
            p=0
            
        if tk>t:
            return 0
            
    
    return 1
    
        
while (pmax-pmin)>1:
    pmid=(pmax+pmin)//2
    if check(pmid)==1:
        pmax=pmid
    else:
        pmin=pmid
        
print(pmax)

Solution (Python):
N, K = map(int, input().split(' '))
w = [int(input()) for _ in range(N)]

def ok(p, k, w):
	sum = 0
	i = 0
	while i < len(w):
		if k == 0:
			return False
		sum += w[i]
		if sum > p:
			k -= 1
			sum = 0
		else:
			i += 1
	return True

l = 0
r = sum(w)
while l+1 < r:
	m = (l+r)//2
	if ok(m, K, w):
		r = m
	else:
		l = m

print(r)