Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

  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.



Sample input:
5 3
8
1
7
3
9


Sample output:
10

Submission status: Accepted

Solution code:
n, k = [ int( val ) for val in raw_input( ).split( " " ) ]
w = [ int( raw_input( ) ) for val in range( n ) ]
sumW = sum( w )
maxW = max( w )

minP = 0
if 1 == k:
	minP = sumW
elif n == k:
	minP = maxW
else:
	left = maxW
	right = 100000*10000
	while left <= right:
		middle = ( left+right )//2
		truckCnt = i = loadings = 0
		while i < n:
			loadings += w[i]
			if middle < loadings:
				truckCnt += 1
				if k < truckCnt+1:
					break
				loadings = w[i]
			i += 1

		if truckCnt+1 <= k:
			minP = middle
		
		if k < truckCnt+1:
			left = middle + 1
		else:
			right = middle - 1

print( minP )

Submission status: Accepted

Solution code:
n, k = [ int( val ) for val in input( ).split( " " ) ]
w = [ int( input( ) ) for val in range( n ) ]
sumW = sum( w )
maxW = max( w )

minP = 0
if 1 == k:
	minP = sumW
elif n == k:
	minP = maxW
else:
	left = maxW
	right = 100000*10000
	while left <= right:
		middle = ( left+right )//2
		truckCnt = i = loadings = 0
		while i < n:
			loadings += w[i]
			if middle < loadings:
				truckCnt += 1
				if k < truckCnt+1:
					break
				loadings = w[i]
			i += 1

		if truckCnt+1 <= k:
			minP = middle
		
		if k < truckCnt+1:
			left = middle + 1
		else:
			right = middle - 1

print( minP )

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
w = [int(input()) for i in range(n)]
l = max(w)
r = sum(w)

while l < r:
    m = (l + r) // 2
    stack = car = 0
    for i in w:
        stack += i
        if stack > m:
            stack = i
            car += 1
    if car < k:
        r = m
    else:
        l = m + 1
print(l)

Submission status: Accepted

Solution code:
import sys

n, k = map(int, input().split())
w = [int(sys.stdin.readline()[:-1]) for i in range(n)]
l = max(w)
r = sum(w)

while l < r:
    m = (l + r) // 2
    stack = car = 0
    for i in w:
        stack += i
        if stack > m:
            stack = i
            car += 1
    if car < k:
        r = m
    else:
        l = m + 1
print(l)

Submission status: Accepted

Solution code:
import sys

n, k = map(int, input().split())
w = [int(sys.stdin.readline()) for i in range(n)]
l = max(w)
r = sum(w)

while l < r:
    m = (l + r) // 2
    stack = car = 0
    for i in w:
        stack += i
        if stack > m:
            stack = i
            car += 1
    if car < k:
        r = m
    else:
        l = m + 1
print(l)

Submission status: Accepted

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


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

left = 1
right = sum(W)
while left < right:
    mid = (left + right) / 2
    v = maxStack(k, mid, W)
    if v >= n:
        right = mid
    else:
        left = mid + 1
print left

Submission status: Accepted

Solution code:
def carriable_baggage(baggage, baggage_num, truck_capacity, truck_num):
    """Return the number of baggae which trucks can carry."""
    laden_baggage = 0
    for i in range(truck_num):
        laden_weight = 0
        while laden_weight + baggage[laden_baggage] <= truck_capacity:
            laden_weight += baggage[laden_baggage]
            laden_baggage += 1
            if laden_baggage == baggage_num:
                return baggage_num
    return laden_baggage

def min_capacity(baggage, baggage_num, truck_num):
    """Return the minimum value of maximum load capacity of trucks."""
    left = 0
    right = 10000 * baggage_num
    while right - left > 1:
        mid = (left + right) // 2
        v = carriable_baggage(baggage, baggage_num, mid, truck_num)
        if v >= baggage_num:
            right = mid;
        else:
            left = mid
    return right


import sys

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

T = list(map(int, sys.stdin))

P = min_capacity(T, n, k)

print(P)

Submission status: Accepted

Solution code:
def carriable_baggage(baggage, baggage_num, truck_capacity, truck_num):
    """Return the number of baggae which trucks can carry."""
    laden_baggage = 0
    for i in range(truck_num):
        laden_weight = 0
        while laden_weight + baggage[laden_baggage] <= truck_capacity:
            laden_weight += baggage[laden_baggage]
            laden_baggage += 1
            if laden_baggage == baggage_num:
                return baggage_num
    return laden_baggage

def min_capacity(baggage, baggage_num, truck_num):
    """Return the minimum value of maximum load capacity of trucks."""
    heaviest_baggage = max(baggage)
    left = 0
    right = heaviest_baggage * baggage_num
    while right - left > 1:
        mid = (left + right) // 2
        v = carriable_baggage(baggage, baggage_num, mid, truck_num)
        if v >= baggage_num:
            right = mid;
        else:
            left = mid
    return right


import sys

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

T = list(map(int, sys.stdin))

P = min_capacity(T, n, k)

print(P)

Submission status: Accepted

Solution code:
def carriable_baggage(baggage, baggage_num, truck_capacity, truck_num):
    """Return the number of baggae which trucks can carry."""
    laden_baggage = 0
    for i in range(truck_num):
        laden_weight = 0
        while laden_weight + baggage[laden_baggage] <= truck_capacity:
            laden_weight += baggage[laden_baggage]
            laden_baggage += 1
            if laden_baggage == baggage_num:
                return baggage_num
    return laden_baggage

def min_capacity(baggage, baggage_num, truck_num):
    """Return the minimum value of maximum load capacity of trucks."""
    left = 0
    right = max(baggage) * baggage_num
    while right - left > 1:
        mid = (left + right) // 2
        v = carriable_baggage(baggage, baggage_num, mid, truck_num)
        if v >= baggage_num:
            right = mid;
        else:
            left = mid
    return right


import sys

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

T = list(map(int, sys.stdin))

P = min_capacity(T, n, k)

print(P)

Submission status: Accepted

Solution code:
def carriable_baggage(baggage, baggage_num, truck_capacity, truck_num):
    """Return the number of baggae which trucks can carry."""
    laden_baggage = 0
    for i in range(truck_num):
        laden_weight = 0
        while laden_weight + baggage[laden_baggage] <= truck_capacity:
            laden_weight += baggage[laden_baggage]
            laden_baggage += 1
            if laden_baggage == baggage_num:
                return baggage_num
    return laden_baggage

def min_capacity(baggage, baggage_num, truck_num):
    """Return the minimum value of maximum load capacity of trucks."""
    left = 0
    right = sum(baggage)
    while right - left > 1:
        mid = (left + right) // 2
        v = carriable_baggage(baggage, baggage_num, mid, truck_num)
        if v >= baggage_num:
            right = mid;
        else:
            left = mid
    return right


import sys

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

T = list(map(int, sys.stdin))

P = min_capacity(T, n, k)

print(P)

Submission status: Accepted

Solution code:
def carriable_baggage(baggage, baggage_num, truck_capacity, truck_num):
    """Return the number of baggae which trucks can carry."""
    laden_baggage = 0
    for i in range(truck_num):
        laden_weight = 0
        while laden_weight + baggage[laden_baggage] <= truck_capacity:
            laden_weight += baggage[laden_baggage]
            laden_baggage += 1
            if laden_baggage == baggage_num:
                return baggage_num
    return laden_baggage

def min_capacity(baggage, baggage_num, truck_num):
    """Return the minimum value of maximum load capacity of trucks."""
    left = max(baggage) - 1
    right = sum(baggage)
    while right - left > 1:
        mid = (left + right) // 2
        v = carriable_baggage(baggage, baggage_num, mid, truck_num)
        if v >= baggage_num:
            right = mid
        else:
            left = mid
    return right


import sys

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

T = list(map(int, sys.stdin))

P = min_capacity(T, n, k)

print(P)

Submission status: Accepted

Solution code:
def carriable_baggage(baggage, baggage_num, truck_capacity, truck_num):
    """Return the number of baggae which trucks can carry."""
    laden_baggage = 0
    for i in range(truck_num):
        laden_weight = 0
        while laden_weight + baggage[laden_baggage] <= truck_capacity:
            laden_weight += baggage[laden_baggage]
            laden_baggage += 1
            if laden_baggage == baggage_num:
                return baggage_num
    return laden_baggage

def min_capacity(baggage, baggage_num, truck_num):
    """Return the minimum value of maximum load capacity of trucks."""
    left = 0
    right = 1000000000
    while right - left > 1:
        mid = (left + right) // 2
        v = carriable_baggage(baggage, baggage_num, mid, truck_num)
        if v >= baggage_num:
            right = mid
        else:
            left = mid
    return right


import sys

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

T = list(map(int, sys.stdin))

P = min_capacity(T, n, k)

print(P)

Submission status: Accepted

Solution code:
#coding:utf-8
#1_4_D
def is_carriable(w_lim, trucks, loads):
    """ Check whether w_lim(maximum carrying capacity) is possible or not """
    i = 0
    while trucks > 0:
        w = 0
        while i < len(loads):
            if w + loads[i] > w_lim:
                trucks -= 1
                break
            w += loads[i]
            i += 1
        if i == len(loads):
            return True
    return False

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

left = max(loads)
right = sum(loads) + 1

while right - left > 1:
    mid = (left + right) // 2
    if is_carriable(mid, trucks, loads):
        ans = mid
        right = mid
    else:
        left = mid

if is_carriable(max(loads), trucks, loads):
    ans = max(loads)

print(ans)

Submission status: Accepted

Solution code:
#coding:utf-8
#1_4_D
def is_carriable(w_lim, trucks, loads):
    """ Check whether w_lim(maximum carrying capacity) is possible or not """
    i = w = 0
    while i < len(loads):
        if w + loads[i] > w_lim:
            trucks -= 1
            w = 0
        else:
            w += loads[i]
            i += 1

        if trucks == 0:
            return False
    return True

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

left = max(loads)
right = sum(loads) + 1

while right - left > 1:
    mid = (left + right) // 2
    if is_carriable(mid, trucks, loads):
        ans = mid
        right = mid
    else:
        left = mid

if is_carriable(max(loads), trucks, loads):
    ans = max(loads)

print(ans)

Submission status: Accepted

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


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

lis=[]
a = input()
(nn,kk)=list(map(int,a.split()))
for i in range(nn):
    lis.append(int(input()))
ans = solve(nn,kk,lis)
print(ans)

Submission status: Accepted

Solution code:
MAX = 100000

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

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

n, k = map(int, raw_input().split())
T = []

for i in range(n):
    T.append(input())

ans = solve()

print ans

Submission status: Accepted

Solution code:
def check_p(p):
    global k, ws
    ct, nt = 0, 1
    for w in ws:
        if ct + w <= p:
            ct += w
        else:
            nt += 1
            if nt > k:
                return False
            ct = w
    return True


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

ws = [int(input()) for _ in range(n)]
l, r, p = max(ws), sum(ws), 0

while l < r:
    p = (l + r) // 2
    if check_p(p):
        r = p
    else:
        l = p = p + 1

print(p)

Submission status: Accepted

Solution code:
def check_p(p):
    global k, ws
    lt, nt = 0, 1  # loadage_of_current_truck, num_of_truck
    for w in ws:
        lt += w
        if lt > p:
            nt += 1
            if nt > k:
                return False
            lt = w
    return True


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

ws = [int(input()) for _ in range(n)]
l, r, p = max(ws), sum(ws), 0

while l < r:
    p = (l + r) // 2
    if check_p(p):
        r = p
    else:
        l = p = p + 1

print(p)

Submission status: Accepted

Solution code:
def check(T, p, n, k):
    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

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

left, right = 0, 100000 * 10000

while(right - left > 1):
    mid = int((left + right) / 2)
    if (check(T, mid, n, k) >= n):
        right = mid
    else:
        left = mid

print(right)

Submission status: Accepted

Solution code:
n, k = map(int, raw_input().split())
W = [input() for _ in xrange(n)]

MAX = 100000
T = [0] * MAX

def check(p):
    i = 0
    for j in xrange(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
    while right - left > 1:
        mid = int((right + left) / 2)
        v = check(mid)
        if v >= n:
            right = mid
        else:
            left = mid

    return right

def main():
    ans = solve()
    print ans
    return 0

main()

Submission status: Accepted

Solution code:
n, k = map(int, raw_input().split())
W = [input() for _ in xrange(n)]

def check(p):
    i = 0
    for j in xrange(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
    while right - left > 1:
        mid = int((right + left) / 2)
        v = check(mid)
        if v >= n:
            right = mid
        else:
            left = mid

    return right

def main():
    ans = solve()
    print ans
    return 0

main()

Submission status: Accepted

Solution code:
# coding:utf-8
n, k = map(int,raw_input().split())
ws = []
for _ in xrange(n):
  ws.append(int(raw_input()))

def possible_put_p(p):
  # P??\?????????????????????????????????
  current = 1
  weight = 0
  for w in ws:
    if weight + w <= p:
      weight += w
    else:
      current += 1
      if current > k:
        return False
      weight = w

  if current <= k:
    return True
  else:
    return False

low = max(ws)
high = sum(ws)
while(high - low > 0):
  mid = (low + high) / 2
  if(possible_put_p(mid)):
    high = mid
  else:
    low = mid + 1

print high

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
w = []
for _ in range(n):
    w.append(int(input()))
imax = 100000 * 1000000
imin = 1
while imin < imax:
    imid = (imin + imax) // 2
    track_num = 0
    current = 0
    for i in range(n):
        if w[i] > imid:
            track_num = k
            break
        elif w[i] + current > imid:
            track_num += 1
            current = w[i]
        else:
            current += w[i]
    if track_num < k:
        imax = imid
    else:
        imin = imid + 1
print(imax)

Submission status: Accepted

Solution code:
import sys
import math

def check(k, w, P):
    i = 0
    for t in range(k):
        p = 0
        while p + w[i] <= P:
            p += w[i]
            i += 1
            if i == len(w):
                return True
    return False

def allocate(k, w):
    t = [0] * k
    le = 0
    ri = 100000 * 10000

    while ri - le > 1:
        P = (ri + le) / 2
        if check(k, w, P):
            ri = P
        else:
            le = P
    return ri

if __name__ == "__main__":
    w = sys.stdin.readlines()
    k = int(w[0].split()[1])
    del w[0]
    w = [int(wi) for wi in w]
    print allocate(k, w)

Submission status: Accepted

Solution code:
import sys
'''
	??\?????????????????????
'''
_allinput = []
for inp in sys.stdin:
	_allinput += inp.strip().split(" ")
def _input():
	for put in _allinput:
		yield put
_obj = _input();
def __input():
	return _obj.__next__()
def nextInt():
	return int(__input())

def check(lst,L):
	tot = 1
	curSum = 0
	for i in lst:
		if curSum + i <= L:
			curSum += i
		else:
			curSum = i
			tot += 1
	return tot

def solve(lst,m):
	l,r = max(lst), 100000 * 10000
	while l != r:
		mid = int((l+r)/2)
		if check(lst,mid) <= m:
			r = mid
		else:
			l = mid + 1
	return l


n,m = nextInt(),nextInt()
if m > 0 or n > 0:
	lst = [nextInt() for i in range(0,n)]
	print(solve(lst,m))

Submission status: Accepted

Solution code:

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

        self.a = max(self.W)-1  # >= 0; False
        self.b = sum(self.W)  # <= 10**9; True

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

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

print(Solve().solve())

Submission status: Accepted

Solution code:
import sys

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

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

print lo

Submission status: Accepted

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

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

print hi

Submission status: Accepted

Solution code:

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


def solve():
    left = 0
    right = sum(w) + 1 # ??????????????°???* 1????????????????????§??????
    while right - left > 1:
        mid = (left + right) / 2
        v = check(mid)  # mid == P ??¨???????????§???????????????????????????
        if v >= n:
            right = mid
        else:
            left = mid
            
    return right

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

Submission status: Accepted

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

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

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

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

	return right

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

	ans = solve()
	print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf_8 -*-

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)

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Algorythm
Referenced #1670532 Solution for ALDS1_4_D: Allocation by Chris_Kobayashi

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

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

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

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

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

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

# initial searching range
top = sum(w) # the top of the searching range
bot = max(w) # the bottom of the searching range

# searching until there is no serching range
while top > bot:
    sp = (top + bot) / 2 # the searching point

    tk = 0 # temp index of the trugs
    weight = 0 # temp total weight of a trug

    # check whether it is possible to load all of the luggage
    #  to the trugs in the weight limit of the searching point
    for tw in w:
        if weight + tw <= sp:
            weight += tw
        else:
            tk += 1
            if tk >= k:
                # when impossible, then raise the bottom
                bot = sp + 1
                break
            weight = tw
    else:
        # when possible, then lowering the top
        top = sp

# output MLC
print top

Submission status: Accepted

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

Algorythm
Referenced #1670532 Solution for ALDS1_4_D: Allocation by Chris_Kobayashi

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

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

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

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

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

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

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

def tempf(sp):
    tk = 0 # temp index of the trugs
    weight = 0 # temp total weight of a trug

    # check whether it is possible to load all of the luggage
    #  to the trugs in the weight limit of the searching point
    for tw in w:
        if weight + tw <= sp:
            weight += tw
        else:
            tk += 1
            if tk >= k:
                # when impossible, then raise the bottom
                return False
            weight = tw
    else:
        # when possible, then lowering the top
        return True

# initial searching range
top = sum(w) # the top of the searching range
bot = max(w) # the bottom of the searching range

# searching until there is no serching range
while top > bot:
    sp = (top + bot) / 2 # the searching point

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

# output MLC
print top

Submission status: Accepted

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


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

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


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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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

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

print(solve(ws, n, k))