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):
import sys
readline = sys.stdin.readline
N, K = map(int, input().split())
W = tuple(map(int, sys.stdin.readlines()))
ma = max(W)
def check(x):
    if x < ma:
        return False
    use = 1
    rest = x
    for w in W:
        if rest >= w:
            rest -= w
        else:
            rest = x - w
            use += 1
            if use > K:
                return False
    return True
l = 0
r = sum(W)
while r - l > 1:
    m = (r + l) // 2
    if check(m):
        r = m
    else:
        l = m
print(r)

Solution (Python):



if __name__ == '__main__':

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

    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

    left = 0
    right = 100000 * 10000

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

    print(right)

Solution (Python):
setting = input().split();
package_count = int(setting[0]);
truck_count = int(setting[1]);
packages = [];
for i in range(package_count):
    packages.append(int(input()));

def allocation():
    max_p = sum(packages);
    left = 0;
    right = max_p;
    while left < right:
        mid = (left + right) // 2;
        load = calculate_load(mid);
        if load >= package_count:
            right = mid;
        else:
            left = mid + 1;
    return right;

def calculate_load(p):
    i = 0;
    j = 0;
    current_truck_p = p;
    while i < package_count and j < truck_count:
        if packages[i] <= current_truck_p:
            current_truck_p -= packages[i];
            i += 1;
        else:
            j += 1;
            current_truck_p = p;
    return i;

print(allocation());

Solution (Python):
def decode():
    [n, k] = [int(x) for x in input().split(" ")]
    ws = []
    for _ in range(n):
        ws.append(int(input()))

    return n, k, ws


def check(k, ws, p):
    sum_w = ws[0]
    tr = 1

    for w in ws[1:]:
        if sum_w + w <= p:
            sum_w += w
        else:
            sum_w = w
            tr += 1

            if tr > k:
                return False

    return True


if __name__ == '__main__':
    n, k, ws = decode()

    lo = max(ws)
    hi = sum(ws)

    while lo <= hi:
        p = (lo + hi) // 2

        if check(k, ws, p):
            hi = p - 1
            ans = p
        else:
            lo = p + 1

    print(ans)

Solution (Python):
def imas(hoge_l, p, track):
    s_weights = 0
    now_track = 1
    for val in hoge_l:
        s_weights += val
        if s_weights > p:
            s_weights = val
            now_track += 1
        if now_track > track:
            return False
    return True

num, track = [int(x) for x in input().split()]
hoge_l = list()
for _ in range(num):
    hoge_l.append(int(input()))
left = 0
right = 100000 * 10000

while left < right :
    mid = (right + left) // 2
    if imas(hoge_l, mid, track):
        right = mid 
    else:
        left = mid + 1
        
max_num = max(hoge_l)
if max_num > right:
    right = max_num
print (right)

Solution (Python):
def check(P):
 i=0
 for _ in[0]*k:
  s=0
  while s+w[i]<=P:
   s+=w[i];i+=1
   if i==n: return n
 return i
n,k=map(int,input().split())
w=[int(input())for _ in[0]*n]
l=0;r=n*100000
while r-l>1:
 m=(l+r)//2
 if check(m)>=n:r=m
 else:l=m
print(r)

Solution (Python):
def check(P):
 i=0
 for _ in[0]*k:
  s=0
  while s+w[i]<=P:
   s+=w[i];i+=1
   if i==n: return n
 return i
n,k=map(int,input().split())
w=[int(input())for _ in[0]*n]
l=0;r=n*100000
while r-l>1:
 m=(l+r)//2
 if check(m)>=n:r=m
 else:l=m
print(r)

Solution (Python):
def check(P):
 i=0
 for _ in[0]*k:
  s=0
  while s+w[i]<=P:
   s+=w[i];i+=1
   if i==n: return n
 return i
n,k=map(int,input().split())
w=[int(input())for _ in[0]*n]
l=0;r=n*100000
while r-l>1:
 m=(l+r)//2
 if check(m)>=n:r=m
 else:l=m
print(r)

Solution (Python):
import sys
def f(P):
 i=0
 for _ in[0]*k:
  s=0
  while s+w[i]<=P:
   s+=w[i];i+=1
   if i==n: return n
 return i
n,k=map(int,input().split())
w=list(map(int,sys.stdin.read().splitlines()))
l=0;r=n*100000
while r-l>1:
 m=(l+r)//2
 if f(m)>=n:r=m
 else:l=m
print(r)

Solution (Python):
import sys
def f(P):
 i=0
 for _ in[0]*k:
  s=0
  while s+w[i]<=P:
   s+=w[i];i+=1
   if i==n: return n
 return i
n,k=map(int,input().split())
w=list(map(int,sys.stdin.read().splitlines()))
l=0;r=sum(w)
while r-l>1:
 m=(l+r)//2
 if f(m)>=n:r=m
 else:l=m
print(r)

Solution (Python):
import sys
def f(P):
 i=0
 for _ in[0]*k:
  s=0
  while s+w[i]<=P:
   s+=w[i];i+=1
   if i==n: return n
 return i
n,k=map(int,input().split())
w=list(map(int,sys.stdin.readlines()))
l=0;r=sum(w)
while r-l>1:
 m=(l+r)//2
 if f(m)>=n:r=m
 else:l=m
print(r)

Solution (Python):
import sys
def f(P):
 i=0
 for _ in[0]*k:
  s=0
  while s+w[i]<=P:
   s+=w[i];i+=1
   if i==n: return n
 return i
n,k=map(int,input().split())
w=list(map(int,sys.stdin.readlines()))
l=0;r=sum(w)
while r-l>1:
 m=(l+r)//2
 if f(m)>=n:r=m
 else:l=m
print(r)

Solution (Python):
import sys
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)

Solution (Python):
import sys
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)

Solution (Python):
import sys
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)

Solution (Python):
import sys
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)

Solution (Python):
import sys
n,k=map(int,input().split())
w=list(map(int,sys.stdin.readlines()))
def f():
 i=0
 for _ in[0]*k:
  s=0
  while s+w[i]<=m:
   s+=w[i];i+=1
   if i==n:return n
 return i
l,r=max(w),sum(w)
while l<r:
 m=(l+r)//2
 if f()>=n:r=m
 else:l=m+1
print(r)

Solution (Python):
from collections import deque

nk = input().split(' ')
n = int(nk[0])
k = int(nk[1])
w = []
for i in range(0, n):
  w.append(int(input()))


def allocatable(a, v):
  b = deque(a)
  currentCar = 0
  wSum = 0
  while currentCar < k:
    weight = b.popleft()
    if wSum + weight <= v:
      wSum += weight
    else:
      
      b.appendleft(weight)
      currentCar += 1
      wSum = 0
    
    if not b:
      return True
  
  return not b


def search(a):
  l = 0
  r = 1000000000
  while l + 1 < r:
    i = int((l + r) / 2)
    if allocatable(a, i):
      r = i
    else:
      l = i
  return r

print(search(w))

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

def isAllocatable(p):
  kw, ki = 0, 1
  for w in wi:
    if w > p: return False
    kw += w
    if kw <= p: continue
    ki += 1
    if k < ki: return False
    kw = w
  return True

l = 0
r = sum(wi)
while l + 1 < r:
  p = int((l + r) / 2)
  if isAllocatable(p): r = p
  else: l = p
print(r)

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

def isAllocatable(p):
  kw, ki = 0, 1
  for w in wi:
    if w > p: return False
    kw += w
    if kw <= p: continue
    kw = w
    ki += 1
    if k < ki: return False
  return True

l, r = 0, sum(wi)
while l + 1 < r:
  p = int((l + r) / 2)
  if isAllocatable(p): r = p
  else: l = p

print(r)

Solution (Python):



import sys
import math 

def is_loadable(load, num_truck, w_list):

    excess = load*num_truck - sum(w_list)
    
    cur_load = 0
    
    for w in w_list:
        
        if cur_load + w < load:
            cur_load += w
        elif cur_load + w == load:
            
            cur_load = 0
            num_truck -= 1
            if num_truck < 0:
                return False
        else:
            num_truck -= 1
            if num_truck < 0:
                return False
            excess += load - cur_load
            if excess < 0:
                return False
            
            
            cur_load = w

    
    if (cur_load and num_truck == 0):
        return False
    
    return True

n, num_truck = map(int, sys.stdin.readline().split())

weight = list()
for i in range(n):
    weight.append(int(sys.stdin.readline()))

ave_w = sum(weight) / num_truck
max_w = max(weight)
load = max(max_w, math.ceil(ave_w))
max_ng = load - 1

while True:
    if is_loadable(load, num_truck, weight):
        break
    min_ng = load
    load += 1024

min_ok = load
while True:
    if min_ok == max_ng + 1:
        break
    load = (max_ng + min_ok) // 2
    if is_loadable(load, num_truck, weight):
        min_ok = load
    else:
        max_ng = load

print(min_ok)

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 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 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):
def cnt_car(w, p):
    car = 1
    wi = 0
    for i in w:
        if (wi + i) <= p:
            wi += i
        else:
            car += 1
            wi = i
    return car

n, k = map(int, input().split())
w = [int(input()) for i in range(n)]
p = max(max(w), sum(w) // k)
while True:
    if cnt_car(w, p) <= k:
        print(p)
        break
    else:
        
        if cnt_car(w, p + 100) > k:
            p += 100
        else:
            p += 1

Solution (Python):
import sys


def allocate(count, weights):
    """allocate all packages of weights onto trucks.
    returns maximum load of trucks.

    >>> allocate(2, [1, 2, 2, 6])
    6
    >>> allocate(3, [8, 1, 7, 3, 9])
    10
    """
    def loadable_counts(maxweight):
        n = 0
        l = 0
        c = count
        for w in weights:
            l += w
            if l > maxweight:
                l = w
                c -= 1

            if c <= 0:
                return n

            n += 1
        return n

    i = max(weights)
    j = max(weights) * len(weights) // count

    while i < j:
        mid = (i + j) // 2
        if loadable_counts(mid) < len(weights):
            i = mid + 1
        else:
            j = mid

    return i


def run():
    k, n = [int(i) for i in input().split()]
    ws = []
    for i in sys.stdin:
        ws.append(int(i))

    print(allocate(n, ws))


if __name__ == '__main__':
    run()

Solution (Python):
def calc_k_constP(P):
    tmp_total_w = 0
    tmp_k = 1
    for w in w_s:
        tmp_total_w += w
        if tmp_total_w > P:
            tmp_k += 1
            tmp_total_w = w

    return tmp_k

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

max_w = max(w_s)

left, right = max_w, 10000 * n
while left < right:
    mid = (right + left) // 2
    tmp_k = calc_k_constP(mid)
    if tmp_k <= k:
        right = mid
    else:
        left = mid + 1

print(left)

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

def trucks(p, k):
    t = 0
    c = 1
    for i in range(len(p)):
        if p[i] > k:
            return 1000000
        elif t + p[i] <= k:
            t += p[i]
        else:
            t = p[i]
            c += 1
    return c

minp = int(sum(pack) / k)
maxp = max(pack) * n
while minp < maxp - 1:
    p = int((maxp + minp) / 2)
    if trucks(pack, p) <= k:
        maxp = p
    else:
        minp = p

if trucks(pack, maxp - 1) <= k:
    print(maxp - 1)
else:
    print(maxp)

Solution (Python):

"""
Created on Mon Apr 30 15:18:29 2018
ALDS1-4c
@author: maezawa
"""
def can_load(w, k, p):
    n = len(w)
    m = 0
    tk = 0
    i = 0
    while tk < k:
        if m + w[i] <= p:
            m += w[i]
            i += 1
            if i >= n:
                return n+1
        else:
            m = 0
            tk += 1
    return i


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

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

maxw = max(w)






right = maxw*n
left = maxw
while left<right:
    mid = (right+left)//2
    cl = can_load(w, k, mid)
    if cl == n:
        print(mid)
        break
    elif cl < n:
        left = mid + 1
    else:
        right = mid
print(right)

Solution (Python):

"""
Created on Mon Apr 30 15:18:29 2018
ALDS1-4c
@author: maezawa
"""
def can_load(w, k, p):
    n = len(w)
    m = 0
    tk = 0
    i = 0
    while tk < k:
        if m + w[i] <= p:
            m += w[i]
            i += 1
            if i >= n:
                return n+1
        else:
            m = 0
            tk += 1
    return i


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

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

maxw = max(w)






right = maxw*n
left = maxw
while left<right:
    mid = (right+left)//2
    cl = can_load(w, k, mid)




    if cl < n:
        left = mid + 1
    else:
        right = mid
print(right)

Solution (Python):
import math
def min_sufficient_load(w, k):
    return check(w, k, 0, sum(w))

def check(w, k, p1, p2):
    if k==1:
        return p2
    if p2 - p1 == 1:
        if get_trunk_No(w, p1) == k:
            return max(p1,max(w))
        else:
            return max(p2,max(w))
    m = math.ceil((p1+p2)/2)
    trunk_no = get_trunk_No(w,m)
    if trunk_no > k:
        return check(w, k, m, p2)
    else:
        return check(w, k, p1, m)
def get_trunk_No(w,m):
    temp = 0
    trunk_no = 1
    for i in w:
        if temp + i <= m:
            temp += i
            if temp == m:
                trunk_no += 1
                temp = 0
        else:
            trunk_no += 1
            temp = i
    if temp==0:
        trunk_no-=1
    return trunk_no
if __name__=="__main__":
    n,k = map(int,input().split(" "))
    w = []
    for i in range(n):
        w.append(int(input()))
    print(min_sufficient_load(w,k))

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 i in range(n)]
 
left = max(W)-1; right = sum(W)
while left+1 < right:
    mid = (left + right)//2
    cnt = 1
    now = 0
    for i in W:
        if mid<now+i:
            now=i
            cnt+=1
        else:
            now+=i
    if cnt<=k:
        right=mid
    else:
        left=mid

print(right)

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


def num_v(p):
    v, kp, vp = 0, 1, 0
    for i in range(N):
        while vp + W[i] > p:
            kp += 1
            vp = 0
            if kp > K:
                break

        else:
            vp += W[i]
            v += 1
            continue

        break

    return v


def main():
    left, right = 0, sum(W)

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

        if v == N:
            right = mid
        else:
            left = mid + 1

    print(left)


if __name__ == '__main__':
    main()

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


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 = 100000*10000
    mid = None
    while right - left > 1:
        mid = int((right + left)/2)
        v = check(mid)
        if v >= n:
            right = mid
        else:
            left = mid
    return right

ans = solve()
print(ans)

Solution (Python):
def binary_search(n, k, lw):
    left = 0
    right = max(lw) * n

    while left <= right:
        mid = (left + right)//2
        if is_underweight(n, k, lw, p=mid):
            right = mid - 1
        else:
            left = mid + 1

    if is_underweight(n, k, lw, p=right):
        return right
    else:
        return left

def is_underweight(n, k, lw, p):
    i = 0
    w = 0
    ck = 1
    while i < n:
        if lw[i] > p:
            return False
        rest = p - w
        if lw[i] <= rest:
            w += lw[i]
            i += 1
        else:
            w = 0
            ck += 1
    return ck <= k

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

    p = binary_search(n, k, lw)

    print(p)

if __name__ == '__main__':
    main()

Solution (Python):
def binary_search(n, k, lw):
    left = 0
    right = max(lw) * n

    while left < right:
        mid = (left + right)//2
        if is_underweight(n, k, lw, p=mid):
            right = mid
        else:
            left = mid + 1

    return left

def is_underweight(n, k, lw, p):
    i = 0
    w = 0
    ck = 1
    while i < n:
        if lw[i] > p:
            return False
        rest = p - w
        if lw[i] <= rest:
            w += lw[i]
            i += 1
        else:
            w = 0
            ck += 1
    return ck <= k

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

    p = binary_search(n, k, lw)

    print(p)

if __name__ == '__main__':
    main()

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

max_w = 100000 * 10000
P = 0
left = 0
right = max_w

def check(p):
    sum = 0
    count = 1
    for i in range(n):
        if(sum + w[i] > p):
            count += 1
            sum = w[i]
            if(count > k or w[i] > p):
                return False
        else:
            sum += w[i]

    return True

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

print(P)

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


def search_v(p):
    v = 0
    w = 0
    tmp_k = 1
    ind = 0

    while True:

        if tmp_k > k:
            return v
        if ind == n:
            return n

        tmp = ary[ind]
        if w + tmp <= p:
            w += tmp
            v += 1
            ind += 1
        else:
            w = 0
            tmp_k += 1


max_p = n * 10000
ps = range(max_p + 1)
left = 0
right = max_p

while left + 1 < right:
    mid = (left + right) // 2
    v = search_v(ps[mid])

    if v >= n:
        right = mid
    else:
        left = mid

print(ps[right])

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):

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

def capa(p,k):
    cnt = 0
    pcopy = p
    num = 0
    for back in backList:
        if back > p:
            break
        if back <= pcopy:
            pcopy -= back
            cnt += 1
            continue
        elif back > pcopy:
            if num == k-1:
                return cnt
            pcopy = p - back
            cnt += 1
            num += 1          
    return cnt


p_min = 0
p_max = 100000 * 10000
def biSearch(p_min, p_max):
    p = p_max - p_min
    if p_max - p_min <= 1:
        return p_max
    if p % 2 == 0:
        c = p_min + int(p/2)
    else:
        c = p_min + int((p+1)/2)
    v = capa(c,k)
    if v < n:
        p_min = c
    else:
        p_max = c

    return biSearch(p_min, p_max)
            

p = biSearch(p_min, p_max)
n_init = n
while n_init <= n:
    p -= 1
    n = capa(p,k)

print(p+1)

Solution (Python):
def ok(p, ws, n, k):
    track = 1
    now = 0
    for i in range(n):
        if ws[i] > p:
            return False
        if now + ws[i] > p:
            track += 1
            now = ws[i]
        else:
            now += ws[i]
    if track > k:
        return False
    else:
        return True


nk = input().split()
n = int(nk[0])
k = int(nk[1])
ws = []
for _ in range(n):
    ws.append(int(input()))

p_min = 0
p_max = int(1e+10)
while p_min < p_max:
    p = (p_min + p_max) // 2
    if ok(p, ws, n, k):
        p_max = p
    else:
        p_min = p + 1
print(p_max)

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

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

	return False

left = 0
right = 100000 * 10000
mid = 0

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

print right-1

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

def enough(p,k,w):
    count = 0
    in_truck = 0
    for x in w:
        if x > p:
            return False
        else:
            if in_truck + x > p:
                count += 1
                in_truck = x
            else:
                in_truck += x
    if in_truck > 0:
        count += 1
    return k >= count

maximum = sum(w)
minimum = 1

while True:
    if minimum == maximum:
        break
    else:
        tmpp = (maximum + minimum) // 2
        if enough(tmpp,k,w):
            maximum = tmpp
        else:
            minimum = tmpp + 1

print(minimum)

Solution (Python):
def stdinput():
    from sys import stdin
    return stdin.readline().strip()

def main():
    n, k = map(int, stdinput().split())
    W = list(map(int, [stdinput() for _ in range(n)]))

    l, r = max(W), 100000*10000

    
    while l != r:
        mid = (l + r) // 2
        if calc_tracks(W, mid) <= k:
            r = mid
        else:
            l = mid + 1

    print(l)
        
def calc_tracks(W, P):
    ret = 0
    current_w = 0
    for w in W:
        if current_w + w > P:
            ret += 1
            current_w = w
        else:
            current_w += w
    return ret + 1

if __name__ == '__main__':
    main()

Solution (Python):
import sys

def check_alloc(weights, cnt, cpct):	
	num = 1
	cur = 0
	for i in range(len(weights)):
		w = weights[i]
		if cur + w > cpct:
			cur = w
			num += 1
			if num > cnt or cur > cpct:
				return False
		else:
			cur += w
	return True

n, k = map(int, input().split())
weights = [0] * n
sum = 0
maxi = 0
for i in range(n):
	weight = int(input())
	weights[i] = weight
	sum += weight
	maxi = max(maxi, weight)

if k == 1:
	print(sum)
	sys.exit()

start = maxi
end = sum
mid = 0
while start <= end:
	mid = int(start + (end - start) / 2)
	can_alloc = check_alloc(weights, k, mid)
	if can_alloc == False:
		start = mid + 1
	else:
		if start == end: break
		end = mid

print(mid)

Solution (Python):
import sys

def check_alloc(weights, k, cpct):
	num = 1
	cur = 0
	for i in range(len(weights)):
		w = weights[i]
		if cur + w > cpct:
			cur = w
			num += 1
			if num > k or cur > cpct:
				return False
		else:
			cur += w
	return True

n, k = map(int, input().split())
weights = [0] * n
sum = 0
maxi = 0
for i in range(n):
	w = int(input())
	weights[i] = w
	sum += w
	maxi = max(maxi, w)

if k == 1:
	print(sum)
	sys.exit()

start = maxi
end = sum
cpct = 0
while start <= end:
	cpct = int(start + (end - start) / 2)
	check = check_alloc(weights, k, cpct)
	if check == False:
		start = cpct + 1
	else:
		if start == end: break
		end = cpct
	
print(cpct)

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

hi = sum(w)
lo = max(w)

def canMove(w, P, k):
    s = 0
    for i in range(len(w)):
        if s + w[i] > P:
            s = 0
            k -= 1
            if k <= 0: return False
        s += w[i]
    return True

P = hi
while lo < hi:
    m = (lo + hi) // 2
    if canMove(w, m, k):
        P = m
        hi = m
    else:
        lo = m + 1

print(P)

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

def canMove(w, P, k):
    s = 0
    for i in range(len(w)):
        if s + w[i] > P:
            s = 0
            k -= 1
            if k <= 0: return False
        s += w[i]
    return True

hi = sum(w)
lo = max(w)

P = hi
while lo < hi:
    m = (lo + hi) // 2
    if canMove(w, m, k):
        P = m
        hi = m
    else:
        lo = m + 1

print(P)

Solution (Python):
import sys

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 = map(int, sys.stdin.readline().strip().split())
w = []
for i in range(n):
    w.append(int(sys.stdin.readline()))

L = max(w)
if check(L):
    print(L)
else:
    R = sum(w)
    assert check(R)

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

    print(R)

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 = map(int, input().strip().split())
w = []
for i in range(n):
    w.append(int(input()))

L = max(w)
if check(L):
    print(L)
else:
    R = sum(w)
    assert check(R)

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

    print(R)

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

N, K = MI()
W = [0] * N
for i in range(N):
    w = I()
    W[i] = w


def is_ok(arg):
    
    cnt = 0
    w_sum = 0
    for i in range(N):
        w_sum += W[i]
        if w_sum > arg:
            cnt += 1
            w_sum = W[i]
        elif w_sum == arg:
            cnt += 1
            w_sum = 0
        else:
            cnt += 0
    if w_sum != 0:
        cnt += 1
    return cnt <= K


def meguru_bisect(ng, ok):
    '''
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng ok は  とり得る最小の値-1 とり得る最大の値+1
    最大最小が逆の場合はよしなにひっくり返す
    '''
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

a = max(W)
b = sum(W)
print(meguru_bisect(a - 1, b + 1))

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

def f(P):
    tmp_capacity = P
    num_used_truck = 1
    i = 0
    while i <= N-1:
        if w[i] > P:
            return i
        if w[i] > tmp_capacity:
            tmp_capacity = P
            num_used_truck += 1
            if num_used_truck >= K+1:
                return i

        tmp_capacity -= w[i]
        i += 1
    
    return i

left = 0
right = 1e9
mid = right
flag = 0
while right - left > 1:
    mid = (left + right)//2
    tmp = f(mid)
    if tmp >= N:
        right = mid
    elif tmp < N:
        left = mid
print(int(right))

Solution (Python):
from sys import stdin

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

def Solve():
    l = 0
    r = 100000 * 100000
    while r - l > 1:
        m = (l + r) // 2
        v = Check(m)
        if v == n:
            r = m
        else:
            l = m
    return r

n, k = map(int, stdin.readline().split())
W = [int(x) for x in stdin.readlines()]

print(Solve())

Solution (Python):
def luggage_num(P):
    i = 0
    for _ in range(k):
        t = 0
        while t + w[i] <= P:
            t += w[i]
            i += 1
            if i == n:
                return n
    return i

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

right = n * max(w)
left = 0

while right - left > 1:
    mid = int((right + left) / 2)
    if luggage_num(mid) >= n:
        right = mid
    else:
        left = mid
print(right)

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

left = 0
right = 10000 * n

def Chech(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)  


while right - left > 1:
    mid = (left+right)//2
    v = Chech(mid,k,W)

    if v >= n:
        right = mid
    else:
        left = mid

print(right)