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:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys
import math 

def is_loadable(load, num_truck, w_list):

    excess = load*num_truck - sum(w_list)
    # print('Minimum Load:', load, num_truck, 'excess:', excess)
    cur_load = 0
    #truck_load = list()
    for w in w_list:
        #print(cur_load, w)
        if cur_load + w < load:
            cur_load += w
        elif cur_load + w == load:
            #truck_load.append(cur_load + w)
            cur_load = 0
            num_truck -= 1
            if num_truck < 0:
                return False
        else:
            num_truck -= 1
            if num_truck < 0:
                return False
            excess += load - cur_load
            if excess < 0:
                return False
            #print(cur_load, 'is added')
            #truck_load.append(cur_load)
            cur_load = w

    #truck_load.append(cur_load)
    if (cur_load and num_truck == 0):
        return False
    #print(truck_load)
    return True

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

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

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

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

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

print(min_ok)

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

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

Submission status: Accepted

Solution code:
import sys


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

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

            if c <= 0:
                return n

            n += 1
        return n

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

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

    return i


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

    print(allocate(n, ws))


if __name__ == '__main__':
    run()

Submission status: Accepted

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

    return tmp_k

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

max_w = max(w_s)

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

print(left)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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


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

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

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

Submission status: Accepted

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


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

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

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

Submission status: Accepted

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

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

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

print(right)

Submission status: Accepted

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


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

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

        break

    return v


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

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

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

    print(left)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

# 最大積載量をPとした時, k台のトラックでどの荷物まで積めるのか
def check(P):
    i = 0
    for j in range(k):
        s = 0
        while s + W[i] <= P:
            s += W[i]
            i += 1
            if i == n: return n
    return i

# 2分探索する
def solve():
    left = 0
    right = 100000*10000
    mid = None
    while right - left > 1:
        mid = int((right + left)/2)
        v = check(mid)
        if v >= n:
            right = mid
        else:
            left = mid
    return right

ans = solve()
print(ans)

Submission status: Accepted

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

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

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

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

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

    p = binary_search(n, k, lw)

    print(p)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

    return left

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

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

    p = binary_search(n, k, lw)

    print(p)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

    return True

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

print(P)

Submission status: Accepted

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


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

    while True:

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

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


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

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

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

print(ps[right])

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:
#coding:utf-8
   
n, k = map(int, input().split())
backList = []
for i in range(n):
    backList.append(int(input()))

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


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

    return biSearch(p_min, p_max)
            

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

print(p+1)

Submission status: Accepted

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


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

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

Submission status: Accepted

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

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

	return False

left = 0
right = 100000 * 10000
mid = 0

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

print right-1

Submission status: Accepted

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

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

maximum = sum(w)
minimum = 1

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

print(minimum)

Submission status: Accepted

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

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

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

    # 二分探索で上限値を確認する
    while l != r:
        mid = (l + r) // 2
        if calc_tracks(W, mid) <= k:
            r = mid
        else:
            l = mid + 1

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

if __name__ == '__main__':
    main()
    # import cProfile
    # cProfile.run('main()')

Submission status: Accepted

Solution code:
import sys

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

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

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

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

print(mid)

Submission status: Accepted

Solution code:
import sys

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

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

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

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

Submission status: Accepted

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

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

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

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

print(P)

Submission status: Accepted

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

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

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

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

print(P)

Submission status: Accepted

Solution code:
import sys

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

n, k = map(int, sys.stdin.readline().strip().split())
w = []
for i in range(n):
    w.append(int(sys.stdin.readline()))

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

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

    print(R)

Submission status: Accepted

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

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

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

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

    print(R)

Submission status: Accepted

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

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


def is_ok(arg):
    # 条件を満たすかどうか？問題ごとに定義
    cnt = 0
    w_sum = 0
    for i in range(N):
        w_sum += W[i]
        if w_sum > arg:
            cnt += 1
            w_sum = W[i]
        elif w_sum == arg:
            cnt += 1
            w_sum = 0
        else:
            cnt += 0
    if w_sum != 0:
        cnt += 1
    return cnt <= K


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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
from sys import stdin

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

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

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

print(Solve())

Submission status: Accepted

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

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

right = n * max(w)
left = 0

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

Submission status: Accepted

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

left = 0
right = 10000 * n

def Chech(P,k,arr):
    weight = 0
    n_trucks = 1
    for i,a in enumerate(arr):
        # iの荷物について積むかどうか決め、それに応じてトラックの数を増加させる
        if P < a:
            return i
        if weight +a <= P:
            weight += a
        else:
            n_trucks += 1  # Pを超えるなら次のtruckを用意
            weight = a  # 新たなトラックに積んでいる
        if n_trucks == k + 1:  # k+1台目のtruckは存在しない。これまでに積んだ荷物の数を返す
            return i

    return len(arr)  # すべて運べるならlen(arr)を返すとする

# right - left > 0　だと無限ループに入るっぽい
while right - left > 1:
    mid = (left+right)//2
    v = Chech(mid,k,W)

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

print(right)

Submission status: Accepted

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

def n_loads(P):
  num = 0
  for _ in range(k):
    w_sum = 0
    while num < n and w_sum + w[num] <= P:
      w_sum += w[num]
      num += 1
  return num

P_lb, P_min = 0, max(w)*(n//k + 1)
while P_min - P_lb > 1:
  P_mid = (P_lb + P_min) // 2
  if n_loads(P_mid) < n:
    P_lb = P_mid
  else:
    P_min = P_mid
print(P_min)

Submission status: Accepted

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

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

left = 0 
right = 100_000 * 10_000

while left < right - 1:
    P = (right + left) // 2
    i = 0
    for _ in range(k):
        if i == n: break
        s = 0
        while s + W[i] <= P:
            s += W[i]
            i += 1
            if i == n: break
    if i >= n:
       right = P
    else:
       left = P
print(right)

Submission status: Accepted

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

def check(x):
    global w
    global n,k
    track=0
    now=0
    for i in w:
        if i>x:
            return False
        if now+i>x:
            track+=1
            now=i
        else:
            now+=i
    if now>0:
        track+=1
    if track>k:
        return False
    else:
        return True
amax=1000000000
amin=0
while amin+1!=amax:
    amid=(amax+amin)//2
    if check(amid):
        amax=amid
    else:
        amin=amid
    
print(amax)

Submission status: Accepted

Solution code:
import sys

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

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

left = 0
right = 100000 * 10000

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

print(right)

Submission status: Accepted

Solution code:
#define k from p
def calck(all_w, p):
    count = 0
    sum = 0
    for w in all_w:
        if sum + w <= p:
            sum += w
        else:
            count+=1 
            sum = w
    return count+1

#get n and k
n, k =map(lambda x: int(x), input().split(' '))

#get all w
#set min and max of p
all_w = []
max = -1
sum = 0
for i in range(n):
    w = int(input())
    all_w.append(w)
    if w > max:
        max = w
    sum += w
max_weight = max
sum_weight = sum
min, max = max, sum
#binary search of p

while min<=max:
    p_pointer = (min+max)//2
    calcedk = calck(all_w, p_pointer)
    if calcedk > k:
        min = p_pointer+1
    elif p_pointer == max_weight or calck(all_w, p_pointer-1) > k:
        print(p_pointer)
        break
    else:
        max = p_pointer-1

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
num, count = map(int, input().split())
baggages = [int(input()) for _ in range(num)]

def check(capacity):
    index = 0
    for _ in range(count):
        weight = 0
        while weight + baggages[index] <= capacity:
            weight += baggages[index]
            index  += 1

            if index == num:
                return num
    return index


L,R = 0, 100000*10000
while R - L > 1:
    pivot = (L + R) // 2
    v = check(pivot)
    if v >= num:
        R = pivot
    else:
        L = pivot
print(R)

Submission status: Accepted

Solution code:
import sys

n, truck_num = map(int, input().split())
weights = [int(x) for x in map(int, sys.stdin)]


def main():
    # 最小値と最大値をもとに二分探索する
    print(binary_search(max(weights), sum(weights)))


def binary_search(left, right):
    """二分探索

    :param left: 最小値
    :param right: 最大値
    :return:
    """

    while left < right:
        # 真ん中の値を割り当てる
        middle = (left + right) // 2

        # 真ん中の値で一旦シミュレート
        if simulate(middle, weights, truck_num):
            # OKならば、最大値をシミュレートした値に
            right = middle
        else:
            # NGならば、最小値をシミュレートした+1に
            left = middle + 1

    return left


def simulate(mid, wei, t_num):
    """

    :param mid: 中央値
    :param wei: 荷物が格納されたリスト
    :param t_num: トラックの台数
    :return: シミュレートOKかNGか
    """
    count = 1
    tmp = 0
    for w in wei:
        tmp += w

        # 積載量(tmp)が求める答え(mid)より大きくなったら
        if mid < tmp:
            # tmpを次の積載物に初期化
            tmp = w
            count += 1
            if t_num < count:
                return False
    return True


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def check(n, k, w, 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
    
n, k = map(int, input().split())
w = [int(input()) for _ in range(n)]

left, right = 0, 10 ** 10

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

print(right)