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

def update(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

left = 0
right = 1e+9

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

    v = update(mid)
    if(v >= n):
        right = mid
    else:
            left = mid

print(right)

Submission status: Accepted

Solution code:
import math

n,k = (int(x) for x in input().split())
w = list()

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

def check(P):
    i = 0
    for j in range(0, k):
        summ = 0
        while(summ + w[i] <= P):
            summ += w[i]
            i += 1
            if(i == n): #最後までしまえたら終了
                return n

    return i #入りきらなかったら終了

def Binary_Search():
    left = 0
    right = 100000*100000
    while(right - left > 1):
        mid = math.floor((left + right) / 2)
        if(check(mid) >= n): #全部トラックに入ったなら範囲の最大値をを狭める
            right = mid
        else:
            left = mid

    return right

ans = Binary_Search()

print(ans)

Submission status: Accepted

Solution code:
def check(w,k,mid):
  weight=mid
  remains=k
  flag=True
  for i in range(len(w)):
    if weight>=w[i]:
      weight-=w[i]
    else:
      remains-=1
      if remains==0:
        flag=False
        break
      weight=mid
      weight-=w[i]

  return flag



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

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

left=max(w)
right=sum(w)
mid=0

while(1):
  mid=int((left+right)/2)
  #print(left,mid,right)
  if check(w,k,mid):
    right=mid
  else:
    left=mid+1

  if left>=right:
    print(left)
    break

Submission status: Accepted

Solution code:
MAX=100000
def Allocate(A, p, k, n):
    count=1
    s=0     
    index=0
    while index<n:
        if s+A[index]<=p:
            s+=A[index]
            index+=1
        else:
            count+=1
            s=0
        if count>k:
            return False

    return True
         
    
n, k=map(int,input().split())
A=[int(input()) for i in range(n)]
left=0
right=MAX*MAX
while left+1<right:
    mid=left+(right-left)//2
    if Allocate(A,mid,k,n):
        right=mid
    else:
        left=mid
print(right)

Submission status: Accepted

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

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

left = max(w)
right = 100000 * 10000
mid = (left+right)//2
ans = right

def check(P):
    tmp_sum = 0
    cnt = 1
    for loop in range(n):
        if tmp_sum + w[loop] <= P:
            tmp_sum += w[loop]
        else:
            tmp_sum = w[loop]
            cnt += 1
            if cnt > k:
                return False
    return True

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

print(ans)

Submission status: Accepted

Solution code:
def main():
    N, K = (int(i) for i in input().split())
    w = [int(input()) for i in range(N)]
    S = 0
    for i in range(N):
        S += w[i]

    def is_ok(P):
        w_i = 0
        for i in range(K):
            cur = 0
            while w_i < N :
                if cur + w[w_i] <= P:
                    cur += w[w_i]
                    w_i += 1
                else:
                    break
        if w_i == N:
            return True
        else:
            return False

    def binary_search_meguru():
        left = -1
        right = S + 1
        while right - left > 1:
            mid = left + ((right - left) // 2)
            if is_ok(mid): 
                right = mid
            else: 
                left = mid
        return right
    
    print(binary_search_meguru())


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def can(l, k, p):
    s, a = 0, 0
    for li in l:
        if li > p: return False
        s += li

        if s > p:
            s = li
            k -= 1
        if k <= 0: return False
        
    return True

def bi(array, k, l, r):
    m = (l + r) // 2
    if l > r:
        return max(l, r)
    b = can(array, k, m)
    if b:
        return bi(array, k, l, m-1)
    else:
        return bi(array, k, m+1, r)
        
    
n, k = map(int, input().split())
l = [0] * n
for i in range(n):
    l[i] = int(input())
    
p = sum(l)
print(bi(l, k, 0, p))

Submission status: Accepted

Solution code:
n, k = map(int, (input().split()))
w_list = [int(input()) for _ in range(n)]
left = max(w_list)-1
right = sum(w_list)

while (right-left) > 1:
    mid = (left + right)//2
    count = 1
    c = 0
    for w in w_list:
        if mid < c + w:
            ｃ = w
            count += 1
        else:
            c += w
    if count <= k:
        right = mid
    else:
        left = mid
print(right)

Submission status: Accepted

Solution code:
def check(P):
    lis = [[] for i in range(k)]
    su = [0 for i in range(k)]
    
    su.append(-10000)
    cur = 0
    for i, bag in enumerate(baggage):
        #cur = 0
        #print(su,cur,su[cur])
        while su[cur] + bag > P:
            cur += 1
        if cur == k:
            return False
        else:
            lis[cur].append(bag)
            su[cur] += bag
    #print(lis, su, P)
    return True

def main():
    min_P = 1000000000
    left = 1
    right = 1000000000
    mid = (left + right)//2
    while  left < right:
        '''if (left + right) % 2 == 0:
            mid = (left + right)//2
        else:
            mid = (left + right)//2 + 1
        #print(left, mid, right, end=" ")'''
        
        if check(mid):
            right = mid
            if min_P > mid:
                min_P = mid
        else:
            left = mid + 1
        mid = (left + right)//2
    #print(left,right)
    print(min_P)
if __name__ == '__main__':
    n, k = map(int, input().rstrip().split(" "))
    #n,k= 5,3
    baggage = [int(input()) for i in range(n)]
    #baggage = [8,1,7,3,9]
    
    main()

Submission status: Accepted

Solution code:
n = list(map(int, input().split()))
w = [0] * n[0]
for i in range(n[0]):
    w[i] = int(input())
    
def check(p):
    i = 0
    for j in range(n[1]):
        s = 0
        while s + w[i] <= p:
            s += w[i]
            i += 1
            if i == n[0]:
                return True
    return False

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

solve()

Submission status: Accepted

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

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

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

print(Binaryserch())

Submission status: Accepted

Solution code:
def track(A, n, k, P): # 最大積載量Pを決めた時，何個の荷物を載せることができるかを返す
	i = 0
	for _ in range(k):
		weight_of_track_j = 0
		while weight_of_track_j + A[i] <= P:
			weight_of_track_j += A[i]
			i += 1
			if i == n:
				return n
	return i


if __name__ == "__main__":
	n, k = map(int, input().split())
	w = []
	for _ in range(n):
		w.append(int(input()))
	left = 0
	right = 100000 * 10000 # トラックの数 * 荷物の最大重み
	key = n
	while right - left > 1:
		mid = (left + right) // 2
		if key > track(w, n, k, mid):
			left = mid
		else:
			right = mid
	print(right)

Submission status: Accepted

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


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

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

    left = 1
    right = 10000 * 100000  # 最大重量 × 最大貨物数

    while left < right:
        mid = (left + right) // 2
        # print("left:{}".format(left))
        # print("right:{}".format(right))
        # print("mid:{}".format(mid))

        v = allocate(mid, k, products)
        # print("count:{}".format(v))

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

    print(right)


def allocate(capacity, truckNum, products):
    # print("===== start allocation capacity:{}======".format(capacity))
    v = 0
    tmp = 0
    truckNum -= 1
    while len(products) > v:
        product = products[v]

        # print("tmp weight:{}".format(tmp))
        # print("product weight:{}".format(product))

        if product > capacity:
            # print("capacity over")
            # そもそも１個も乗らない時避け
            return 0

        if tmp + product <= capacity:
            # 同じトラックに積み続ける
            tmp += product
        else:
            # 新しいトラックがまだあればつむ
            if truckNum > 0:
                # print("new truck")
                truckNum -= 1
                tmp = product
            else:
                return v

        v += 1

    return v


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/4/ALDS1_4_D
# 工夫すればO(logn)ぐらいで解けるかもしれないが、nは最大で10**5。なのでO(nlogn)でもギリギリ間に合う(1.7*10**6回ぐらい)
# Pを与えたときにk台のトラックに詰める荷物の量を返す関数(O(n))を設計すれば二分探索でO(nlogk)で処理できる。
# Pを与えたときに何台のトラックが必要かを返す関数(O(n))でもおk

# イメージとしては単調増加関数を経由して二分探索する感じ


# %%
def n_nimotu_if_P(P, k, arr):  # Pに対する単調増加関数
    weight = 0
    n_trucks = 1  # 1台目から積んでいく
    for i, a in enumerate(arr):
        # iの荷物について積むかどうか決め、それに応じてトラックの数を増加させる
        if P < a:  # P<aの時点で即時終了 絶対その荷物は積めないので
            return i  # i個の荷物が詰める(i-1番目までの荷物が積める)

        if weight + a <= P:  # Pを超える手前までどんどん積んでいく
            weight += a
        else:
            n_trucks += 1  # Pを超えるなら次のtruckを用意
            weight = a  # 新たなトラックに積んでいる

        if n_trucks == k+1:  # k+1台目のtruckは存在しない。これまでに積んだ荷物の数を返す
            return i  # (i-1番目までのi個の荷物が積める)

    # truckに余裕があるなら全部詰める
    return len(arr)  # すべて運べるならlen(arr)を返すとする。


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

# 探索する配列が未知のため、pythonのbisectは使えない状況。自分で実装
# n_nimotui_if_P()==n ならば 荷物を全部運んだ(もしくは余裕があるということ)。
# ==ならPを小さくし<ならばPを大きくしていく二分探索で解ける

left, right = 0, 10000 * n
i_break = 0
while right - left > 1:
    mid = (left+right)//2
    if n <= n_nimotu_if_P(mid, k, luggages):  # もし余裕があるならPを減らす
        right = mid  # ギリギリOKなのはrightに最終的に格納されているはず
    else:  # 余裕がなければ(n>n_nimotu_if_P())、Pを増やす
        left = mid

print(right)

Submission status: Accepted

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

P = 10 ** 4 * 10 ** 5

mi = 0
ma = P

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

print(ma)

Submission status: Accepted

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

#input = open(sys.argv[1], "r").readline

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

    # (lb, ub] の間を二分探索
    lb = max(W)-1   # 最大の w さえ積めれば良い場合が p の取り得る最小値
    ub = sum(W)     # 全てを 1 台のトラックに積む必要がある場合が p の取り得る最大値

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

        v = 0
        k = 1
        for w in W:
            if v + w <= p: # 積載オーバーしなければ積む
                v += w
            else:
                k += 1
                v = w

        if k <= K:
            # p が条件を満たしている ⇒ 解の存在範囲を (lb, p] に更新
            ub = p
        else:
            # p が条件を満たしていない ⇒ 解の存在範囲を (p, ub] に更新
            lb = p
#        print(p,k,lb,ub)

    # この時点で lb + 1 = ub となっている
    print(ub)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

#print(check(4))
#print(check(5))
#print(check(6))
#print(check(7))

Submission status: Accepted

Solution code:
#ALDS1_4_D Allocaion
def check(k, w, p):  # 積載制限 p 台数 k のトラックに乗り切るか確認
    j = 0
    for i in range(k):
        sum = 0
        while sum < p:
            if sum + w[j] > p:
                break
            else:
                sum += w[j]
                j += 1
            if j == len(w):  # 積載完了
                break
        if j == len(w):
            break

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


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

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

while True:
    mid = (left + right) // 2
    # print('mid : {}'.format(mid))

    if check(k, w, mid):
        right = mid
    else:
        left = mid
    if right - left <= 1:
        break
    # print('left : {}  right : {}'.format(left, right))

print(right)

Submission status: Accepted

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

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

Submission status: Accepted

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


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

P_max = n * 10000 // k + 10001

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

print(r)

Submission status: Accepted

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

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

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

print(search(M-1,S))

Submission status: Accepted

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

Submission status: Accepted

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

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


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


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

print(ans)

Submission status: Accepted

Solution code:
import sys

def value(w,n,P):

	tmp_w = 0
	k = 1

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


def test():

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

	max = 0
	sum = 0

	for i in range(n):

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

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

		sum += w[i]

	while max != sum:

		mid = (max + sum) // 2

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


	print(max)

if __name__ == "__main__":
	test()

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n,k=map(int, input().split( ))
w = []
for _ in range(n):
    w.append(int(input()))
mx=sum(w)
mn=max(w)##mx//k<max(w)が抜けてる
mid = (mx+mn)//2
w.append(1000000000000000)

while mn < mid:#このループ条件が不自然みたいだが
    cnt = 1
    sm = 0
    for i in range(n):#ここがwhileだったのを修正して減らした
        if sm <= mid-w[i]:
            sm +=  w[i]
        else:
            cnt+=1
            sm = w[i]

    if cnt>k:
        mn = mid
        mid = (mid+mx)//2
    else:
        mx = mid
        mid = (mid+mn)//2
#最終的な実行可能解が不明、結局最後mn,mid,mx全部チェックしてる
ans=[]
for a in [mn,mid,mx]:
    cnt = 1
    sm = 0
    for i in range(n):
        if sm <= a - w[i]:
            sm +=  w[i]
        else:
            cnt+=1
            sm = w[i]

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

print(min(ans))
#最終的な実行可能解は(直前までmidだった)mx

Submission status: Accepted

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

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

      if k < trucks:
        return False

  return True

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

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

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

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import math

tr = []

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

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

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

print left

Submission status: Accepted

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

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

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

  # kの積載量に対してトラックに詰めこむ操作の二分法で探索する。
  right = sum(w) # 解の上界
  left = sum(w)//n # 平均を床関数とったものが下界
  max_weight = left
  while right-left > 1:
    # print(left,right,max_weight)
    if check_load(k, w, max_weight):
      right = max_weight
    else:
      left = max_weight

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
tmp=[int(input()) for i in range(n)]
 
left=max(tmp)-1
right=sum(tmp)
while left+1 < right:
    mid=(left+right)//2
    count=1
    now=0
    for i in tmp:
        if mid<now+i:
            now=i
            count+=1
        else:
            now+=i
 
    if count<=k:
        right=mid
    else:
        left=mid
print(right)

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:
from collections import deque
from enum import Enum
import sys
import math
 
BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001
 
 
N,K = map(int,input().split())
 
table = [0]*N
max_W = 0
 
for i in range(N):
    table[i] = int(input())
    max_W = max(max_W,table[i])
 
 
left = max_W;right = 10000*100000;mid = (left+right)//2;
ans = right
 
 
def is_ok(tmp_P):
 
    num_track = 1
    tmp_sum = 0
    for i in range(N):
 
        if tmp_sum+table[i] <= tmp_P:
            tmp_sum += table[i]
        else:
            num_track += 1
            tmp_sum = table[i]
            if num_track > K:
                return False
 
    return True
 
 
while left <= right:
 
    if is_ok(mid) == True:
        ans = mid
        right = mid-1
    else:
        left = mid+1
 
    mid = (left+right)//2;
 
 
print("%d"%(ans))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
W_MAX = 10000
K_MAX = 100000


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


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from typing import List


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


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

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

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

        mid_weight = (left_weight + right_weight) // 2

    print(f"{optimal_P}")

Submission status: Accepted

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

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

    def solve():
        left = 0
        right = total + 1
        
        while right > left:
            mid = (right + left)//2
            c = check(mid) # 检查当每辆车的装载量为 mid 时，最多能装多少件货物
            if c >= n:
                right = mid
            else:
                left = mid + 1
        return right

    print(solve())

Submission status: Accepted

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

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

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

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