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:
import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque
import copy

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def req_count(P, K, W):
    cnt = 0
    for k in range(K):
        p = 0
        while p + W[cnt] <= P:
            p += W[cnt]
            cnt += 1
            if cnt == len(W):
                return cnt
    else:
        return cnt


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, K = il()
    W = [ii() for _ in range(N)]

    left, right = 0, sum(W)
    while right - left != 1:
        middle = (left + right) // 2
        n = req_count(middle, K, W)
        if n >= N:
            right = middle
        else:
            left = middle
    print(right)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
n, k = map(int, input().split())
num = [int(input()) for i in range(n)]
#num.sort()
left = max(max(num), math.ceil(sum(num)/k))
right = sum(num)
while left < right:
    mid = (left + right) // 2
    track = 1
    cnt = 0
    flag = 0
    for i in num:
        cnt += i
        if cnt > mid:
            track+=1
            cnt = i
        if track > k:
            flag = 1
            break
        if flag:
            break
    if flag == 0:
        right = mid
    else:
        left = mid+1
print(left)

Submission status: Accepted

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


def is_loadable(pack: list, k: int, P: int):
    _tmp = 0
    counter = 1
    for w in pack:
        if _tmp + w > P:
            _tmp = w
            counter += 1
        else:
            _tmp += w
        if counter > k or w > P:
            return False
    return True


n, k = [int(i) for i in input().strip().split()]
pack = [None] * n
for i in range(n):
    pack[i] = int(input())

right = sum(pack)
left = max(pack)

while left < right:
    mid = (left + right) // 2
    if is_loadable(pack, k, mid):
        right = mid
    else:
        left = mid + 1

print(left)

Submission status: Accepted

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

def judge(x):
    now, cnt = 0, 0
    
    for i in range(n):
        if now+w[i]<=x:
            now += w[i]
        else:
            cnt += 1
            now = w[i]
    
    if now>0:
        cnt += 1
    
    return cnt<=k

def binary_search():
    l, r = max(w), 10**10
    
    while l<=r:
        m = (l+r)//2
        
        if judge(m):
            r = m-1
        else:
            l = m+1
    
    return l

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from collections import deque
n, k = input().rstrip().split(" ")
n = int(n)
k = int(k)
w_list = deque()
for _ in range(n):
    w_list.append(int(input().rstrip()))

def get_num_of_w(p, w_list, k):
    w_cnt = 0
    k_cnt = k
    temp_p = p
    temp_w_list = w_list.copy()

    while k_cnt > 0 and len(temp_w_list) > 0:
        w = temp_w_list[0]
        temp_p -= w
        if temp_p >= 0:
            temp_w_list.popleft()
            w_cnt += 1
        else:
            temp_p = p
            k_cnt -= 1
    return w_cnt  

    
left = 0
right = 10000 * 100000
min_p = 10000 * 100000
while left < right:
    mid = (left+right) // 2
    if get_num_of_w(mid, w_list, k) >= n:
        right = mid
        min_p = mid
    else:
        left = mid + 1
    
print(min_p)

Submission status: Accepted

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

# 荷物の最大積算量を返す
def check(p):
    global n,k,w
    v = 0
    track = 0
    temp = 0
    i = 0
    while track < k:
        temp = 0
        while temp + w[i] <= p:
            temp += w[i]
            i = i + 1
            if i == n:
                return i
        track += 1
        #print(track,i)
    return i

def main():
    global n,k,w
    left = 0
    right = 100000*10000

    while True:
        mid = int( (left+right) / 2 )
        #print(left,right,mid)
        v = check(mid)
        judge = check(mid-1)
        #print(n,v,judge)
        if v < n:
            left = mid + 1
        elif v == n and judge != n:
            return mid
        elif v == n and judge == n:
            right = mid

print(main())

Submission status: Accepted

Solution code:
def is_ok(W, truck, middle):
    loaded = 0
    for t in range(truck):
        this_total = 0
        while this_total + W[loaded] <= middle:
            this_total += W[loaded]
            loaded += 1
            if loaded == len(W):
                return True
    return False

def meguru_bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(w, k, mid):
            ok = mid
        else:
            ng = mid
    return ok

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

w = [0]*n
for i in range(n):
    w[i] = int(input())

ans = meguru_bisect(-1,10**10+1)
print(ans)

Submission status: Accepted

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

def binarySearch(left,right):
    mid = 0
    while right > left:
        mid = int(left + (right - left)//2)
        if check(mid,w,k):
            right = mid
        else:
            left = mid + 1
    return left

def check(p,w,k):
    k_tmp = 1
    w_tmp = 0
    for w_i in w:
        w_tmp += w_i
        if w_tmp > p:
            w_tmp = w_i
            k_tmp += 1
            if k_tmp > k:
                return False
    return True

print(binarySearch(max(w),sum(w)))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from sys import stdin
import math

n, k = map(int, stdin.readline().split())
w = list([int(stdin.readline().rstrip()) for i in range(n)])

def main2():
  def is_ok():
    cnt_track = w_tmp = 0
    for w_i in w:
      w_tmp += w_i
      if w_tmp > m:
        w_tmp = w_i
        cnt_track += 1
        if cnt_track >= k:
          return 0
    return 1

  r = sum(w)
  l = max(math.ceil(r/k),max(w))
  while l < r:
    m = (l + r) // 2
    # print("%d %d %d " % (l, r, m))
    if is_ok():
      r = m
    else:
      l = m + 1
  print(r)

if __name__ == '__main__':
  main2()

Submission status: Accepted

Solution code:
def canLoad(n, k, p):
    global w
    load = 0
    for i in range(n):
        load += w[i]
        if load <= p:
            continue
        k -= 1
        if k == 0:
            return False
        load = w[i]
    return True

def solve(n, k, pmin, pmax):
    if pmin + 1 >= pmax:
        return pmax
    newp = (pmax + pmin) // 2
    if canLoad(n, k, newp):
        return solve(n, k, pmin, newp)
    else:
        return solve(n, k, newp, pmax)

n, k = map(int, input().split())
w = [0]*n
wsum = 0
wmax = 0
for i in range(n):
    w[i] = int(input())
    wsum += w[i]
    if w[i] > wmax:
        wmax = w[i]

# p の最小の候補は wmax と ceil(wsum/k) の最大値
pmin = max(wmax, wsum // k if wsum % k == 0 else wsum // k + 1)
pmax = wsum
p = pmin
if not canLoad(n, k, pmin):
    p = solve(n, k, pmin, pmax)
print(p)

Submission status: Accepted

Solution code:
p_max = 100000 * 10000

nk = list(map(int, input().split()))
w = [int(input()) for i in range(nk[0])]


def search(pt):
    m = 0
    for j in range(nk[1]):
        weight = 0
        while weight + w[m] <= pt:
            weight += w[m]
            m += 1
            if m == nk[0]:
                return nk[0]
    return m


def main():
    st_p = p = 0
    en_p = p_max
    while en_p - st_p > 1:
        p = int((en_p + st_p) / 2)
        chk = search(p)
        if chk >= nk[0]:
            en_p = p
        else:
            st_p = p
    return en_p


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
def unit_check(n, k, w_list, P):
    i = 0
    for j in range(k):
        weight = 0
        while weight + w_list[i] <= P:
            weight += w_list[i]
            i += 1
            if i == n:
                return 1
    return 0

n, k = map(int,input().split())
w_list = [0] * n
for i in range(n):
    w_list[i] = int(input())

left = 0
right = 100000*10000
while left+1 < right:
    mid = (left+ right)//2
    check = unit_check(n, k, w_list, mid)
    if check == 1:
        right = mid
    else:
        left = mid
print(right)

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:
import sys
import math

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

W = []
for _ in range(n):
    w = int(sys.stdin.readline())
    W.append(w)

r = sum(W)
l = max(W)
pre_p = 0


while l < r:

    current = 0
    num_tracks = 1

    p = (l + r) // 2  # 値を設定

    # 積み込めるか確認
    for w in W:
        if current + w > p:
            num_tracks += 1  # 次のトラックを持ってくる
            current = w
        else:
            current += w
    
    if num_tracks > k:  # 現在の p ではトラックが足りない場合
        l = p + 1  # 最少値を上げる
    else:
        r = p  # 最大値を下げる


print(l)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
    
n,k = map(int, input().split())
w = [int(input()) for i in range(n)]

def get_v(n,k,w,P):
    c = 0
    val = 0
    for i in w:
        val += i
        if val > P:
            c += 1
            val = i
            if c >= k:
                return 0
    return 1

left = max(w)
right = sum(w)
while True:
    P = (left + right)//2
    ret = get_v(n,k,w,P)
    if ret:
        right = P
    else:
        left = P + 1
    if left == right:
        break
print(left)

Submission status: Accepted

Solution code:
def check(m):
    global n, k, w, presum
    s = 0
    for j in range(k):
        ok = s
        ng = n + 1
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if presum[mid] - presum[s] <= m:
                ok = mid
            else:
                ng = mid
        s = ok
    if s == n:
        return True
    else:
        return False


def resolve():
    global n, k, w, presum
    n, k = [int(i) for i in input().split()]
    w = [int(input()) for _ in range(n)]
    presum = [0 for _ in range(n + 1)]
    for i in range(n):
        presum[i + 1] = presum[i] + w[i]
    if n <= k:
        print(max(w))
        return
    ok = 100000 * 10000
    ng = 0
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid
    print(ok)


resolve()

Submission status: Accepted

Solution code:
def check(p):
    j = 0 # 積んだ荷物の個数
    for i in range(k):
        track = 0
        while track + w[j] <= p:
            track += w[j]
            j += 1
            if j == n:
                return n
    return j

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

    return mid

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

print(solve())

Submission status: Accepted

Solution code:
from __future__ import print_function

import sys
sys.setrecursionlimit(500000)

import re
import array
import copy
import functools
import operator

import math
import string
import fractions
from fractions import Fraction

import collections
import itertools
import bisect

import random
import time

import heapq
from heapq import heappush
from heapq import heappop
from heapq import heappushpop
from heapq import heapify
from heapq import heapreplace
from queue import PriorityQueue as pq
from queue import Queue

from itertools import accumulate

from collections import deque
from collections import Counter

from operator import mul
from functools import reduce

input = sys.stdin.readline


def eprint(*args, **kwargs):
    print(*args, file=sys.stderr, **kwargs)
    return

# from fractions import gcd
# from math import gcd

# def lcm(n, m):
#     return int(n * m / gcd(n, m))


# def coprimize(p, q):
#     common = gcd(p, q)
#     return (p // common, q // common)


# def find_gcd(list_l):
#     x = reduce(gcd, list_l)
#     return x


# def combinations_count(n, r):
#     r = min(r, n - r)
#     numer = reduce(mul, range(n, n - r, -1), 1)
#     denom = reduce(mul, range(1, r + 1), 1)
#     return numer // denom


# mod=1000000007
# def combinations_count_mod(n, r):
#     r = min(r, n - r)
#     numer = reduce(lambda x,y: x*y%mod, range(n, n - r, -1), 1)
#     denom = pow( reduce(lambda x,y: x*y%mod, range(1, r + 1), 1) , mod-2, mod)
#     return numer * denom % mod

def is_ok(p,n,k,w):
    #
    i_track = 0
    i_w = 0

    # トラックに積めるギリギリ(p)まで積んでいくことを繰り返していって，
    # i_w(w_index) を0 ~ n-1 まで全部積めたら嬉しいねぇ
    # 積載量pが小さすぎるゴミみてぇなトラックだったら先にトラックの数が尽きてしまって悲しいことになります
    # 積載量pが十分大きい素敵なトラックだったら i_w(w_index) = n - 1 まで到達できてとっても嬉しくなれます
    while i_track < k and i_w < n : # トラック全部
        temp=0
        while i_w < n and temp + w[i_w] <= p: #  一時積載tempがpを超えないギリギリを目指していけ
            temp += w[i_w]
            i_w+=1
        # ギリギリまで ，背番号i_trackのトラック ，つまり今見ているトラックに積載したら
        i_track += 1 #次のトラックに進みましょうね〜〜〜

    return i_w == n

def solve(n,k,w):
    # 
    ok = 10000 * 100000  # solve(ok)は解が存在すると分かっているような整数ok
    ng = -1                # solve(ng)は解が存在しない(と分かっているような整数ng
    ans = ok

    # abs(ok-ng) つまり ok と ng の絶対差ですね，これが1未満つまりokとngが等しいということになったらですね，終了するんですね
    while abs( ok - ng ) > 1: #abs(ok-ng) <= 1 というのはokとngがもうなんかね，アレなんですよ
        mid = (ok + ng) // 2
        # 
        if is_ok(mid,n,k,w):
            ok = mid
            ans = ok
        else:
            ng = mid
    return ans

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from typing import List


def count_loadable_baggage_num(baggage_num: int, truck_num: int, baggages: List[int], truck_capacity: int) -> int:
    loaded_baggage_num: int = 0

    for _ in range(truck_num):
        current_weight: int = 0
        while current_weight + baggages[loaded_baggage_num] <= truck_capacity:
            current_weight += baggages[loaded_baggage_num]
            loaded_baggage_num += 1
            if loaded_baggage_num == baggage_num:
                return baggage_num

    return loaded_baggage_num


def calc_turck_min_capacity(baggage_num: int, truck_num: int, baggages: List[int]) -> int:
    ng: int = max(baggages) - 1
    ok: int = sum(baggages) + 1

    while ok - ng > 1:
        mid = (ng + ok) // 2
        loadable_baggage_num = count_loadable_baggage_num(baggage_num, truck_num, baggages, mid)
        if loadable_baggage_num >= baggage_num:
            ok = mid
        else:
            ng = mid

    return ok


def main():
    n, k = map(int, input().split())
    w: List[int] = []

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

    P = calc_turck_min_capacity(n, k, w)
    print(P)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def check(P):
	global n, k, L
	i = 0
	for j in range(k):
		s = 0
		while s + L[i] <= P:
			s += L[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

print(solve())

Submission status: Accepted

Solution code:
from sys import stdin

def solve_howmany_trucks(P):
    '''
    トラックの数がk、最大積載量がPのとき荷物を載せきれるかを判定する
    '''
    truck = 1
    temp_weight = 0
    for a,b in enumerate(w):
        if b > P:
            return False
        if temp_weight + b > P:
            # print(f"P = {P} truck No {truck} temp_weight {temp_weight+b}")
            truck += 1
            if truck > k:
                return False
            temp_weight = b
        else:
            temp_weight += b

    return True



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

w = [int(input()) for a in range(n)]

min_P = 10000*100000
left = 0
right = min_P
while left != right:
    middle = int((left+right)/2)
    if solve_howmany_trucks(middle):
        right = middle
    else:
        left = middle+1
print(left)

Submission status: Accepted

Solution code:
def Count_car(n,k,S,P):
    storage = 0
    number = 1
    for i in range(n):
        weight = S[i]
        if storage + weight > P:
            storage = weight
            number += 1
        else:
            storage += weight
    if number > k:return 0
    return 1
n,k = list(map(int,input().split()))
total = 0
M = 0
S = []
for _ in range(n):
    number = int(input())
    S.append(number)
import math
P = max(max(S),math.ceil(sum(S)/k))
Q = sum(S)
while True:
    if Q - P <= 1:
        if Count_car(n,k,S,P):
            break
        else:
            P = P+1
            break
    mid = (P+Q)//2
    if Count_car(n,k,S,mid):
        Q = mid
    else:
        P = mid
print(P)

Submission status: Accepted

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

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

left = 0
right = 100000*10000

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

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:
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    n, k = LI()
    Q = [I() for _ in range(n)]

    def can_stack(p):
        s = 0
        truck_num = 1
        for i in Q:
            if s+i<=p:
                s += i
            else:
                truck_num += 1
                s = i
        return truck_num<=k

    ng = max(Q)-1
    ok = sum(Q)
    while abs(ok-ng)>1:
        m = (ng+ok)//2
        if can_stack(m):
            ok = m
        else:
            ng = m
    print(ok)

    # for i in range(20):
    #     print(i, can_stack(i))

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
def ok(p,w,k):
    track= 1
    weight= 0
    flag= True
    for i in w:
        if i > p:
            flag=False
            break
        elif weight+ i> p:
            weight= i
            track+= 1
        else:
            weight+= i
    if track<=k and flag:
        return True
    else:
        return False
            

n,k= map(int, input().split())
w=[]
for i in range(n):
    w.append(int(input()))
    
l=0
h=10**11
while l+1 < h:
    p= (l+h)//2
    if ok(p,w,k):
        h= p
    else:
        l= p
print(h)

Submission status: Accepted

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

def check(a, p):
    if max(a) > p:
        return False
    else:
        tr = 0
        count = 1
        for i in a:
            tr += i
            if tr > p:
                count += 1
                tr = i
        if count > k:
            return False
        else:
            return True
Min = 0
Max = max(a) * (n // k + 1)

while Min + 1 < Max:
    if check(a, (Min + Max) // 2) == True:
        Max = (Min + Max) // 2
    else:
        Min = (Min + Max) // 2
print(Max)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
w=[int(input()) for i in range(n)]
def ok(p):
  t=[0]*k
  curr=0
  for i in w:
    if i>p:
      return False
    if t[curr]+i>p:
      curr+=1
      if curr>=k:
        return False
    t[curr]+=i
  return True
l=0
h=10**9+1
while True:
  if l>=h:
    print(l)
    break
  if h==l+1:
    print(l if ok(l) else h)
    break
  mid=(l+h)//2
  if ok(mid):
    h=mid
  else:
    l=mid

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15


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

r = 10 ** 10
l = 0
def ok(x):
    cnt = 1
    tot = 0
    for i in range(N):
        if tot + W[i] <= x:
            tot += W[i]
        else:
            cnt += 1
            if W[i] > x:
                return False
            tot = W[i]
    return cnt <= K      

while r - l > 1:
    mid = (r + l)//2
    if ok(mid):
        r = mid
    else:
        l = mid
print(r)

Submission status: Accepted

Solution code:
#Pの時に必要なトラックの数を求める関数
def unit_check(n, k, w_list, P):
    i = 0
    for j in range(k):
        weight = 0
        while weight + w_list[i] <= P:
            weight += w_list[i]
            i += 1
            if i == n:
                return 1
    return 0

n, k = map(int,input().split())
w_list = [0] * n
for i in range(n):
    w_list[i] = int(input())

left = 0
#荷物の最大数x荷物の最大の重さ
right = 100000*10000
while left+1 < right:
    mid = (left+ right)//2
    check = unit_check(n, k, w_list, mid)
    if check == 1:
        right = mid
    else:
        left = mid
print(right)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
w = [int(input()) for i in range(n)]
def f(x):
    i = 0
    for j in range(k):
        s = 0
        while s+w[i] <= x:
            s += w[i]
            i+=1
            if i == n:
                return n
    return i

def bin_search(left,right):
    while right - left > 1:
        mid = (left + right) // 2
        if f(mid) == n:
            right = mid
        else:
            left = mid
    return right

print(bin_search(0,10**9))

Submission status: Accepted

Solution code:
# coding: utf-8
# 二分探索（応用）


def loading(pack_list, k, q):

    truck = 0
    idx = 0
    for pack in pack_list:
        if pack > q:
            return False

        if truck + pack > q:
            idx += 1
            truck = 0

        truck += pack

    if truck > 0:
        idx += 1

    return False if idx > k else True


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

    pack = []

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

    min = 0
    max = int(1E20)
    # min = sum(pack) // n
    # max = sum(pack)

    q = (max + min) // 2

    res = loading(pack, k, q)

    while min + 1 != max:
        min, max = [min, q] if res else [q, max]
        q = (max + min) // 2

        res = loading(pack, k, q)

    print(max)

Submission status: Accepted

Solution code:
def isPacked(numcar, maxweight, packs):
	weight = 0  # 一台当たりの積載量
	k = 1  # トラック台数

	for j in range(len(packs)):
		if packs[j] > maxweight:
			return False
		if weight + packs[j] > maxweight:
			k = k + 1
			weight = packs[j]
		else:
			weight = weight + packs[j]
		if k > numcar:
			return False

	return True


n, k = map(int, input().split())  # 5,3
W = []  # 8, 1, 7, 3, 9
PMAX = 0

for i in range(n):
	W.append(int(input()))
for i in W:
	PMAX = PMAX + i

#print(W)
#print(PMAX)

#print(isPacked(k, 5, W))
left = 0
right = PMAX + 1

while left < right:
	mid = (left + right) // 2
#	print('{0} {1} {2}'.format(left, mid, right))
	booleanPacked = isPacked(k, mid, W)
	if booleanPacked == True and isPacked(k, mid - 1, W) == False:
		print(mid)
		exit(0)
	elif booleanPacked == True:
		right = mid
	elif booleanPacked == False:
		left = mid + 1

Submission status: Accepted

Solution code:
number=list(map(int,input().split()))
count_l=number[0]
count_t=number[1]
luggage=[int(input()) for i in range(count_l)]

min_P=max(max(luggage),sum(luggage)//count_t)
max_P=sum(luggage)
left=min_P
right=max_P

while left<right:
    mid=(left+right)//2
    count_track=1
    flag=1
    load=0
    for i in range(count_l):
        load+=luggage[i]
        if load>mid:
            count_track+=1
            load=luggage[i]

        if count_track>count_t:
            flag=0
            break

    if flag:
        right=mid

    else:
        left=mid+1

print(left)

Submission status: Accepted

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

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


def is_ok(p):
    truck_index = 0
    w_index = 0
    while w_index < n and truck_index < k:
        load_sum = 0
        while w_index < n and load_sum + w[w_index] <= p:
            load_sum += w[w_index]
            w_index += 1
        truck_index += 1
    return w_index == n


ng = 0
ok = 100000 * 100000

while ok - ng > 1:
    mid = (ng + ok) // 2
    if is_ok(mid):
        ok = mid
    else:
        ng = mid

print("%d" % ok)

Submission status: Accepted

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

def isPossibleCarry(k, wi, P):
    track_num = 1
    track_weight = 0
    
    for w in wi:
        if(w > P):
            return False
        
        if(track_weight + w < P):
            track_weight = track_weight + w
        elif(track_weight + w == P):
            track_num += 1
            track_weight = 0
        else:
            track_num += 1
            track_weight = w
            if(track_num > k):
                return False
            
    return track_num <= k or (track_num == k+1 and track_weight==0)

left_P = 1
right_P = sum(wi)
while left_P < right_P:
    mid = int((left_P + right_P) /2)
    if(isPossibleCarry(k, wi, mid)):
        right_P = mid
    else:
        left_P = mid + 1
if(isPossibleCarry(k, wi, mid)):
    print(mid)
else:
    print(left_P)

Submission status: Accepted

Solution code:
from sys import stdin
from math import ceil

def is_stackable(k,p,w):
    if max(w) > p:
        return False
    s = w[0]
    count = len(w)
    for i in range(1, len(w)):
        if s + w[i] <= p:
            s += w[i]
            count -= 1
        else:
            s = w[i]
    return k >= count

def main():
    n,k = map(int, stdin.readline().split())
    w = [int(line) for line in stdin.readlines()]
    
    left = max(max(w), ceil(sum(w)/k))
    right = (max(w) * ceil(n/k)) + 1
    while True:
        mid = int((left + right) / 2)
        if is_stackable(k, mid, w):
            if not is_stackable(k, mid - 1, w):
                print(mid)
                break
            right = mid
        else:
            if is_stackable(k, mid + 1, w):
                print(mid + 1)
                break
            left = mid + 1

main()

Submission status: Accepted

Solution code:

import sys
from sys import stdin
input = stdin.readline

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

# 最大積載Pのトラックで何個の荷物を積めるか
def check(P):
    i = 0
    for j in range(k):
        s = 0
        while  s + w[i] <= P:
            s += w[i]
            i += 1
            if i == n:
                return n
    return i

def solve():
    left = 0
    right = 100000 * 10000  #荷物の個数 * 1個当たりの最大重量

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

print(solve())

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
quantity, num = list(map(int, input().split()))
weights = list(map(int, [input() for _ in range(quantity)]))

def truck_num(max_load, weights):
  num = 1
  tmp = 0
  for w in weights:
    if tmp + w <= max_load:
      tmp += w
    else:
      tmp = w
      num += 1
  return num


left = max(weights)
right = 100000 * 10000

while left != right:
  mid = (left + right) // 2
  x = truck_num(mid, weights)
  if x <= num:
    right = mid
  else:
    left = mid + 1

ans = left
print(ans)