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:

def f(w, n, k, v):
    # how many things in list w of length n can fill in k cars with capacity v?
    i = 0
    space = 0
    while i < n:
        if space >= w[i]:
            space -= w[i]
            i += 1
        else:
            # space < w[i]
            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

    # range: (left, right]
    # loop until left + 1 = right, then right is the answer
    # why? because right works, but right - 1 doesn't work
    # so right is the smallest capacity
    while right - left > 1:
        mid = (left + right) / 2
        v = f(w, n, k, mid)
        if v >= n:
            # range: (left, mid]
            # in fact, v cannot > n
            right = mid
        else:
            # range: (mid, right]
            left = mid
    print right

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
import math


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

W = []

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


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


# PROCESS
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


# OUTPUT
print(P_min)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:


def check(P, k, w): # 最大積載量Pのトラックがk台ある時、積める荷物の個数
    i = 0 # 返値＝積める荷物の個数のカウンター
    n = len(w) # 積まなければならない荷物の総数
    for _ in range(k):# トラックの台数分のループ
        s = 0 # そのトラックの積載量
        while s + w[i] <= P: # トラックに新たな荷物を積んでも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()

Submission status: Accepted

Solution code:
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  # k=1, n=10**5, w=10**4の場合
while right - left > 1:
    mid = (left + right) / 2
    v = can_be_loaded(mid)  # P = midとして何個積めるかチェック
    if v >= N:  # ここに=を入れているので最後がreturn rightでOK
        right = mid
    else:
        left = mid
print(int(right))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
            #break   
    
    return 1
    
        
while (pmax-pmin)>1:
    pmid=(pmax+pmin)//2
    if check(pmid)==1:
        pmax=pmid
    else:
        pmin=pmid
        
print(pmax)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

def is_ok(lug,t,a):#全ての荷物を積載量aで積めるかどうか
    truck_num = 1
    truck = 0
    for i in lug:
        if i > a:
            return False
        truck += i
        if truck ==a:#もしトラックにa分積まれてたらリセット
            truck = 0
            truck_num += 1
        elif truck > a:
            truck = i
            truck_num += 1
    if truck == 0:
        truck_num -= 1
    if truck_num > t:
        return False
    return True

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

max_n = 100000
max_k = 100000
max_w = 10000


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

  i = 0
  for k in range(K):
    s = 0
    while s + T[i] <= p:
      s += T[i]
      i += 1
      if i == N: return N
  return i

def solve():
  left = 0
  right = max_k * max_w

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


if __name__ == '__main__':
  N, K = map(int, input().split())
  T = [int(input()) for _ in range(N)]

  ans = solve()
  print(ans)

Submission status: Accepted

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

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

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

left = start
right = sum + 1

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

Submission status: Accepted

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

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

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

    print(ok)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys


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


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


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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import ceil


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


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

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



left = 0
right = 100000 * 10000

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

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


print(right)

Submission status: Accepted

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


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

Submission status: Accepted

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


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

Submission status: Accepted

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


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

    # Pの数を2分探索で求める
lp, rp = 0, 10000*100000
while lp < rp:
    mp = (lp+rp)//2
    # 探索するPで荷物をいくつ詰めるか求める
    num = loadnum(mp)
    if num >= n:
        rp = mp
    else:
        lp = mp+1

print(lp)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
W = [int(input()) for _ in range(N)]
P_MIN = max(W)
P_MAX = 10 ** 9
while P_MIN < P_MAX:
    P = (P_MAX + P_MIN) // 2  # トラックの最大積載量
    M = 0
    i = 0
    while i < N:  # 最大積載量Pのトラックに荷物がなくなるまで載せる
        mass = 0  # トラックは初め何も載っていない
        while i < N and mass + W[i] <= P:  # 荷物がなくなるか，トラックに積めなくなるまで荷物を載せる
            mass += W[i]
            i += 1
        M += 1  # 使用したトラックの台数が1だけ増える
    if M > K:  # 最大積載量が小さすぎて，トラックが足りない場合
        P_MIN = P + 1
    elif M <= K:  # 逆に最大積載量が大きすぎて，トラックが余る場合
        P_MAX = P
print(P_MIN)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
MAX_P = 100000 * 10000

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


# k台のトラックに、積載量Pでいくつ荷物が載せられるか
# 0 <= r <= n
def check(p):
    k_no = 1
    tmp = 0
    for i, wi in enumerate(w):
        if wi > p:
            return i
        if tmp + wi > p:
            if k_no == k:
                return i
            else:
                k_no += 1
                tmp = wi
        else:
            tmp += wi
    return len(w)


def solve():
    left = 1
    right = MAX_P

    while right - left > 1:
        mid = (left + right) // 2
        v = check(mid)  # v個載せられる
        if v < n:
            left = mid
        else:
            right = mid

    # print("left", left)
    # print("right", right)
    if check(left) >= n:
        return left
    else:
        return right

# for i in range(10):
#     print(i, check(i))

print(solve())

Submission status: Accepted

Solution code:
# coding: utf-8

#最大積載量がPのとき、必要になるトラックの台数を返す
def trackNum(P, wi, n):
    track = 1
    sum = 0
    if P < max(wi):
        return -1
    for i in range(n):
        sum += wi[i]
        if sum > P:
            track += 1
            sum = wi[i]
        elif sum == P and i < n - 1:
            track += 1
            sum = 0
    return track
    
n, k = map(int,input().rstrip().split())
wi = []
for i in range(n):
    wi.append(int(input().rstrip()))
#必要になるトラックがk以下になる最小のPを求める
start = max(wi)
end = sum(wi)
while start < end:
    half = int((start+end)/2)
    if trackNum(half, wi, n) > k:
        start = half
    else: 
        end = half
    if start + 1 == end:
        if trackNum(start, wi, n) <= k:
            end = start
        break

print(end)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


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


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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdin

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

    return p_max

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

    return len(rest)

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

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
import bisect


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

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

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

    print(p_min)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def InputData():
    
    # [weight_len, track_num] = map(int, input().split())
    # weight_data_str = [input() for i in range(weight_len)]
    # weight_data = list(map(int, weight_data_str))

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

    return weight_len, track_num, weight_data

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

    return i

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

    left = 0

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

    return right

def PrintOut(right):
    print(right)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

print("%d"%(ans))

Submission status: Accepted

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

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

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

# 同じ荷物を2回積むことはないので、2重ループでも計算量はO(N)
def check(P):
    # 積んだ荷物の個数
    load = 0
    # トラックの台数ループ
    for j in range(K):
        truck = 0
        # あるトラックに荷物を積み込むループ
        while truck + aN[load] <= P:
            truck += aN[load]
            load += 1
            # 全部積めた
            if load == N:
                return N
    # i個詰めた
    return load

# 2分探索で最初にN個全部積める場所を見つける
hi = 10 ** 9
low = 0
# low+1 == hi -> lowとhiが隣り合った状態なので、境界が確定する
while low+1 < hi:
    mid = (hi+low) // 2
    if check(mid) == N:
        hi = mid
    else:
        low = mid
# hiの位置が最初にN個全部積める積載量S
print(hi)

Submission status: Accepted

Solution code:
import sys

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


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


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

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

print(right)

Submission status: Accepted

Solution code:
#  http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_D&lang=jp
#  Allocatin : python3
#  2018.12.09 yonezawa


#from collections import deque
import sys
input = sys.stdin.readline
#import cProfile

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

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


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

if __name__ == '__main__':
   main()
#    pr = cProfile.Profile()
#    pr.runcall(main)
#    pr.print_stats()