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: Time Limit Exceeded

Solution code:
# coding: UTF-8
#@document_it
from collections import deque
def document_it(func):
    def new_function(*args,**kwargs):
        print('Running function:', func.__name__)
        print('Positional arguments:', args)
        print('Kewword arguments:', kwargs)
        result = func(*args,**kwargs)
        print('Result:', result)
        return result
    return new_function
    
#@document_it
def loadable(p,w,k):
    m = 1
    loaded = False
    while loaded or m <= k:
        sum = 0
        a = 0
        while sum <= p and w:
            a = w.pop()
            sum += a
        #sum > p or w is empty here
        if sum > p:
            w.append(a)
            m += 1
        else:
            loaded = True
            return True
    #外に出ることとnot loaded and m > kが同値になるようにする
    return False

def exe():
    n,k = map(int,input().split())
    upper = 0
    lower = 10000
    w = deque()
    for _ in range(n):
        a = int(input())
        if a < lower:
            lower = a
        upper += a
        w.appendleft(a)
    
    left = lower
    right = upper
    mid = (right + left)//2
    fmax = -1
    tmin = upper
    
    while True:
        mid = (right + left)//2
        #print(left,mid,right)
        wcopy = w.copy()
        if loadable(mid,wcopy,k):
            if  fmax == mid - 1:
                print(mid)
                exit()
            else:
                tmin = mid
                right = mid
        else:
            if  tmin == mid + 1:
                print(mid + 1)
                exit()
            else:
                fmax = mid
                left = mid + 1
        #ループ不変条件
        #[left,right]内に求めるPが存在する
        #tmin以上のpはすべてloadable
        #fmax以下のpはすべてnot loadable

if __name__ == '__main__':
    exe()

Submission status: Time Limit Exceeded

Solution code:
# coding: UTF-8
#@document_it
from collections import deque
def document_it(func):
    def new_function(*args,**kwargs):
        print('Running function:', func.__name__)
        print('Positional arguments:', args)
        print('Kewword arguments:', kwargs)
        result = func(*args,**kwargs)
        print('Result:', result)
        return result
    return new_function
    
#@document_it
def loadable(p,list):
    if not list:
        return 0
    s = 0
    k = 1
    for e in list:
        if e > p:
            return -1
        else:
            ss = s + e
            if ss <= p:
                s = ss
            else:
                k += 1
                s = e
    return k

def exe():
    n,k = map(int,input().split())
    upper = 1000000000
    lower = 1
    w = []
    for _ in range(n):
        w.append(int(input()))
    
    left = lower
    right = upper
    mid = (right + left)//2
    fmax = -1
    tmin = upper
    
    while True:
        mid = (right + left)//2
        #print(left,mid,right)
        test = loadable(mid,w)
        if k >= test and test != -1:
            if  fmax == mid - 1:
                print(mid)
                exit()
            else:
                tmin = mid
                right = mid
        else:
            if  tmin == mid + 1:
                print(mid + 1)
                exit()
            else:
                fmax = mid
                left = mid + 1
        #ループ不変条件
        #[left,right]内に求めるPが存在する
        #tmin以上のpはすべてloadable
        #fmax以下のpはすべてnot loadable

if __name__ == '__main__':
    exe()

Submission status: Time Limit Exceeded

Solution code:
# coding: UTF-8
#@document_it
from collections import deque
def document_it(func):
    def new_function(*args,**kwargs):
        print('Running function:', func.__name__)
        print('Positional arguments:', args)
        print('Kewword arguments:', kwargs)
        result = func(*args,**kwargs)
        print('Result:', result)
        return result
    return new_function

def isloadable(p,list,cand):
    if not list:
        return True
    s = 0
    k = 1
    for e in list:
        if k > cand:
            return False
        if e > p:
            return False
        else:
            ss = s + e
            if ss <= p:
                s = ss
            else:
                k += 1
                s = e
    if k <= cand:
        return True
    else:
        return False
    
#@document_it
def loadable(p,list):
    if not list:
        return 0
    s = 0
    k = 1
    for e in list:
        if e > p:
            return -1
        else:
            ss = s + e
            if ss <= p:
                s = ss
            else:
                k += 1
                s = e
    return k

def exe():
    n,k = map(int,input().split())
    upper = 1000000000
    lower = 1
    w = []
    for _ in range(n):
        w.append(int(input()))
    
    left = lower
    right = upper
    mid = (right + left)//2
    fmax = -1
    tmin = upper
    
    while True:
        mid = (right + left)//2
        #print(left,mid,right)
        #test = loadable(mid,w)
        #if k >= test and test != -1:
        if isloadable(mid,w,k):
            if  fmax == mid - 1:
                print(mid)
                exit()
            else:
                tmin = mid
                right = mid
        else:
            if  tmin == mid + 1:
                print(mid + 1)
                exit()
            else:
                fmax = mid
                left = mid + 1
        #ループ不変条件
        #[left,right]内に求めるPが存在する
        #tmin以上のpはすべてloadable
        #fmax以下のpはすべてnot loadable

if __name__ == '__main__':
    exe()

Submission status: Time Limit Exceeded

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))

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

print(load)

Submission status: Time Limit Exceeded

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(w)
while True:
    if cnt_car(w, p) <= k:
        print(p)
        break
    else:
        p += 1

Submission status: Time Limit Exceeded

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:
        p += 1

Submission status: Time Limit Exceeded

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 sumw(i, j):
        if (i, j) not in sums:
            sums[(i, j)] = sum(weights[i:j])
        elif (i, j-1) in sums:
            sums[(i, j)] = sums[(i, j-1)] + weights[j-1]

        return sums[(i, j)]

    sums = {}
    k = len(weights)
    if count >= k:
        return max(weights)
    elif count == 1:
        return sum(weights)

    maxloads = [sumw(0, i+1) for i in range(k-count+1)]
    for i in range(1, count):
        for j in reversed(range(k - count + 1)):
            ms = []
            for x in range(j+1):
                p1 = i+x
                p2 = i+j+1
                if i == count-1:
                    p2 = k
                ms.append(max(sumw(p1, p2), maxloads[x]))
            maxloads[j] = min(ms)

    return min(maxloads)

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: Time Limit Exceeded

Solution code:
from itertools import combinations

def func(w, partition):
    if len(partition) == 0:
        return sum(w)
    else:
        sum_list = [sum(w[0:partition[0]])]
        for i in range(len(partition)):
            if i < len(partition) - 1:
                sum_list.append(sum(w[partition[i]:partition[i+1]]))
            else:
                sum_list.append(sum(w[partition[i]:]))

        return max(sum_list)


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

w_indices = [i for i in range(1, n)]
partition_list = combinations(w_indices, k-1)
p_list = []
for partition in partition_list:
    p_list.append(func(w, partition))

print(min(p_list))

Submission status: Time Limit Exceeded

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

max_w = max(w_s)

while True:
    tmp_total_w = 0
    tmp_k = 1
    for w in w_s:
        tmp_total_w += w
        if tmp_total_w > max_w:
            tmp_k += 1
            tmp_total_w = w

    if tmp_k <= k:
        break

    max_w += 1

print(max_w)

Submission status: Time Limit Exceeded

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 and i < n:
        if m + w[i] <= p:
            m += w[i]
            i += 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

Submission status: Time Limit Exceeded

Solution code:
#coding: Shift_JIS

str=input().split()
n=int(str[0])
k=int(str[1])
w=[0]*n
for i in range(n):
	w[i]=int(input())

def pile(tmp,ptr):
	if ptr<n and tmp>=w[ptr]:
		tmp-=w[ptr]
		ptr+=1
		return pile(tmp,ptr)
	return ptr

p=0
ptr=0
while ptr!=n:
	p+=1
	ptr=0
	for i in range(k):
		if w[ptr]>p: break
		tmp=p
		ptr=pile(tmp,ptr)
		if ptr==n: break
print(p)

Submission status: Time Limit Exceeded

Solution code:
#coding: Shift_JIS

str=input().split()
n=int(str[0])
k=int(str[1])
w=[None]*n
max=0
max_ptr=-1
sum=0

for i in range(n):
	w[i]=int(input())
	if max<w[i]:
		max=w[i]
		max_ptr=i

def pile(tmp,ptr,dif):
	if ptr>=0 and ptr<n and tmp>=w[ptr]:
		tmp-=w[ptr]
		ptr+=dif
		return pile(tmp,ptr,dif)
	return ptr

p=max
while p*n<sum: p+=1
while 1:
	cnt=0
	ptr=max_ptr
	while cnt<=k and ptr>=0:
		ptr=pile(p,ptr,-1)
		cnt+=1
	ptr=max_ptr+1
	while cnt<=k and ptr<n:
		ptr=pile(p,ptr,1)
		cnt+=1
	if cnt<=k: break
	p+=1


print(p)

Submission status: Time Limit Exceeded

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_min == p_max:
        return p_min
    if p % 2 == 0:
        p = int(p/2)
    else:
        p = int((p+1)/2)
    v = capa(p,k)
    if v < n:
        p_min = p_min + p
    else:
        p_max = p_min + p

    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: Time Limit Exceeded

Solution code:

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:
				return False
		else:
			cur += w	
	return True

n, k = map(int, input().split())
weights = [0] * n
cpct = 0
for i in range(n):
	weight = int(input())
	weights[i] = weight
	cpct = max(cpct, weight)
	
while True:	
	can_alloc = check_alloc(weights, k, cpct)
	if can_alloc == False:
		cpct += 1
	else:
		break

print(cpct)

Submission status: Time Limit Exceeded

Solution code:

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
cpct = 0
for i in range(n):
	weight = int(input())
	weights[i] = weight
	cpct += weight

cpct = int(cpct/k)
while True:	
	can_alloc = check_alloc(weights, k, cpct)
	if can_alloc == False:
		cpct += 1
	else:
		break

print(cpct)

Submission status: Time Limit Exceeded

Solution code:

def check_alloc(weights, cnt, cpct, st, stn):	
	num = 1
	cur = stn
	for i in range(st, len(weights)):
		w = weights[i]
		if cur + w > cpct:
			if num == 1:
				st = i
				stn = cur
			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
cpct = 0
for i in range(n):
	weight = int(input())
	weights[i] = weight
	cpct += weight

cpct = int(cpct/k)
st = 0
stn = 0
while True:
	can_alloc = check_alloc(weights, k, cpct, st, stn)
	if can_alloc == False:
		cpct += 1
	else:
		break

print(cpct)

Submission status: Time Limit Exceeded

Solution code:
def takein(p):
    s = 0
    track = 1
    for i in range(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()))

p = max(max(w), sum(w) // k)
while not takein(p):
    p += 1

print(p)

Submission status: Memory Limit Exceeded

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

# print(loads)
slices = []


def slicing(rest, s):
    if not rest:
        slices.append(s+[(len(s) and s[-1][1], len(loads))])
        return

    first = len(s) and s[-1][1]
    for s1 in range(first+1, len(loads)-rest+1):
        slicing(rest-1, s+[(first, s1)])


slicing(tracks-1, [])
# print(slices)


def load_count_max(load):
    # print(load, max(sum(loads[l[0]: l[1]]) for l in load))
    return max(sum(loads[l[0]: l[1]]) for l in load)


result = min(map(load_count_max, slices))
print(result)

Submission status: Memory Limit Exceeded

Solution code:
import sys
import math

def is_capable(n, k, w, P):
    track = 0
    cnt = 0
    i = 0

    while cnt < k:
        if i == n:
            return True

        if track + w[i] > P:
            track = 0
            cnt += 1
        else:
            track += w[i]
            i += 1

    return False
    pass

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

'''
print(n,k)
print(w)
'''

# ????????¨

if k == 1:
    ans = sum(w)
    print(ans)
elif n == 1:
    ans = w[0]
    print(ans)
else:
    max_p = sum(w)
    min_p = math.ceil(max_p / k) - 1

    capable = [None] * (max_p - min_p + 1)
    capable[0] = False
    capable[-1] = True

    bottom = 0
    top = len(capable)

    while bottom < top:
        mid = (bottom + top) // 2

        if capable[mid] is None:
            capable[mid] = is_capable(n, k, w, min_p + mid)

        if capable[mid] == True:
            if capable[mid - 1] is None:
                capable[mid - 1] = is_capable(n, k, w, min_p + mid - 1)

            if capable[mid - 1] == False:
                bnd = mid
                break
            else:
                top = mid
        elif capable[mid] == False:
            if capable[mid + 1] is None:
                capable[mid + 1] = is_capable(n, k, w, min_p + mid + 1)

            if capable[mid + 1] == True:
                bnd = mid + 1
                break
            else:
                bottom = mid + 1

    ans = min_p + bnd

    print(ans)
    # print(capable)

Submission status: Accepted

Solution code:
def Is_ToPut(p,w,k):
    count =1
    temp =p
    for i in w:
        if temp >= i:
            temp -=i
        elif i > p :
            return 0
        else:     
            count +=1
            temp =p-i
    if count <= k:return 1
    else:return 0

n,k = list(map(int,input().split(' ')))
w =[]
for _ in range(n):
    w.append(int(input()))
ans =100000*10000
left = 0
right = 100000*10000
while left < right:
    p = (left+right)//2
    if Is_ToPut(p,w,k):
        if ans > p:ans =p
        right=p
    else:
        left = p +1
print(ans)

Submission status: Accepted

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

ma = sum(wlist) + 1
mi = max(wlist) - 1
while (ma - mi > 1):
    mid = (ma + mi)//2
    truck = [0for i in range(k)] ## k개
    i = 0
    gobigger = 0
    for w in wlist:
        if(truck[i] + w <= mid):
            truck[i] = truck[i] + w
        else:
            i = i+1
            if (i == k):
                gobigger = 1
                break
            truck[i] = truck[i] + w
    if (gobigger == 1):
        mi = mid
    else:
        ma = mid
    
print(ma)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
W = [int(input()) for _ in range(n)]
def can_load(W, k, q, n):
    i = 0
    for _ in range(k):
        s = 0
        while i < n and s + W[i] <= q:
            s += W[i]
            i += 1
    if i == n:
        return True
    else:
        return False

# 積載量をmidと仮定して二分探索
hi = 10 ** 9  # OK
lo = 0  # NG
while hi - lo > 1:
    mid = (hi + lo) // 2
    if can_load(W, k, mid, n):
        hi = mid
    else:
        lo = mid
print(hi)

Submission status: Accepted

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

w = []

for i in range(n):
    w.append(int(input()))
   
def carriable(P, n, k, w):
    j = 0
    for i in range(k):
        sum = 0
        while j < n and sum + w[j] <= P:
            sum += w[j]
            j += 1
    return j

def binary_search(p_left, p_right, n, k, w):
    if p_left == p_right:
        return p_left
    else:
        p_center = (p_left + p_right)//2
        # because we have to search for the smallest p which satisfies carriable(p, n, k, w) = n, 
        # be careful of the inequality condition
        if carriable(p_center, n, k, w) >= n:
            return binary_search(p_left, p_center, n, k, w)
        else:
            return binary_search(p_center + 1, p_right, n, k, w)

p_left = 0
p_right = sum(w)
print(binary_search(p_left, p_right, n, k, w))

Submission status: Accepted

Solution code:
def allocate(n,w,k,p):
	t=0
	c=1
	for i in range(n):
		if t + w[i] > p:
			t=0
			c+=1
			if c > k:
				return -1
		t+=w[i]
	return 0

n,k=map(int,input().split())
w=[0]*n
m=(1<<30)*-1
s=0
for i in range(n):
	w[i]=int(input())
	m=max(m,w[i])
	s+=w[i]

i=m
j=s
while (i<=j):
	guess = int(i+(j-i)/2)
	if allocate(n,w,k,guess) < 0:
		i = guess + 1
	else:
		j = guess - 1
print(i)

Submission status: Accepted

Solution code:
def is_leq_S(A, lim, K):
    S = [0] * K

    ai = 0
    si = 0

    while ai < len(A):
        if S[si] + A[ai] <= lim:
            S[si] += A[ai]
            ai += 1
        else:
            si += 1

            if si == K:
                return False
    
    return True


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

    l = 0
    r = 100000 * 100000

    while l + 1 < r:
        m = (l + r) // 2

        if is_leq_S(A, m, K):
            S = m
            r = m
        else:
            l = m

    print(S)
    

main()

Submission status: Accepted

Solution code:
def can_load(num_baggages, baggages, num_truck, max_load):
    bag_no = 0

    for i in range(num_truck):
        load_cap = max_load
        while load_cap > 0:
            if bag_no >= num_baggages:
                #print(max_load, "True")
                return True
            if load_cap >= baggages[bag_no]:
                load_cap -= baggages[bag_no]
                bag_no += 1
            else:
                break
    #print(max_load, bag_no >= num_baggages)
    return bag_no >= num_baggages

def main():
    num_baggages, num_trucks = map(int, input().split())
    baggages = [int(input()) for x in range(num_baggages)]

    start = max(sum(baggages) // num_trucks, min(baggages))
    end = sum(baggages)

    while start < end:
        mid = (start + end) // 2
        if can_load(num_baggages, baggages, num_trucks, mid):
            end = mid
        else:
            start = mid + 1

    print(start)
    return


main()

Submission status: Accepted

Solution code:
import sys
def can_load(num_baggages, baggages, num_truck, max_load):
    bag_no = 0

    for i in range(num_truck):
        load_cap = max_load
        while load_cap > 0:
            if bag_no >= num_baggages:
                #print(max_load, "True")
                return True
            if load_cap >= baggages[bag_no]:
                load_cap -= baggages[bag_no]
                bag_no += 1
            else:
                break
    #print(max_load, bag_no >= num_baggages)
    return bag_no >= num_baggages

def main():
    num_baggages, num_trucks = map(int, input().split())
    baggages = list(map(int, sys.stdin.read().splitlines()))

    start = max(sum(baggages) // num_trucks, min(baggages))
    end = sum(baggages)

    while start < end:
        mid = (start + end) // 2
        if can_load(num_baggages, baggages, num_trucks, mid):
            end = mid
        else:
            start = mid + 1

    print(start)
    return


main()

Submission status: Accepted

Solution code:
import sys
def can_load(num_baggages, baggages, num_truck, max_load):
    bag_no = 0

    for i in range(num_truck):
        load_cap = max_load
        while load_cap > 0:
            if bag_no >= num_baggages:
                #print(max_load, "True")
                return True
            if load_cap >= baggages[bag_no]:
                load_cap -= baggages[bag_no]
                bag_no += 1
            else:
                break
    #print(max_load, bag_no >= num_baggages)
    return bag_no >= num_baggages

def main():
    num_baggages, num_trucks = map(int, input().split())
    baggages = tuple(map(int, sys.stdin.read().splitlines()))

    start = max(sum(baggages) // num_trucks, min(baggages))
    end = sum(baggages)

    while start < end:
        mid = (start + end) // 2
        if can_load(num_baggages, baggages, num_trucks, mid):
            end = mid
        else:
            start = mid + 1

    print(start)
    return


main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
l = list(int(input()) for i in range(n))

left = max(l)-1; right = sum(l)

while left+1 < right:  #最大値と合計値の間のどこかに考えるべき値が存在する
    mid = (left + right) // 2
    cnt = 1; cur = 0  #初期化
    for a in l:
        if mid < cur + a:
            cur = a
            cnt += 1
        else:
            cur += a

    if cnt <= k:
        right = mid
    else:
        left = mid

print(right)

Submission status: Accepted

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

def solve():
    left   = 0
    right  = 10**5 * 10**4
    middle = 0
    while(right-left > 1):
        middle = (left+right)//2
        v = check(middle)
        if(v >= len(n_list)):
            right = middle
        else:
            left = middle
    return right

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

Submission status: Accepted

Solution code:
def check(p):
    i = 0
    for _ in range(k):
        total = 0
        while total+n_list[i] <=p:
            total += n_list[i]
            i += 1
            if i == n:
                return n
    return i

def solve():
    left   = 0
    right  = 10**5 * 10**4
    middle = 0
    while right - left > 1:
        middle = (left+right)//2
        temp_ans = check(middle)
        if temp_ans >= n:
            right = middle
        else:
            left  = middle
    return right

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

Submission status: Accepted

Solution code:
import math
from typing import List

buggage_num, truck_num = map(int, input().split())
buggage_list = [int(input()) for i in range(buggage_num)]


def able_to_load_buggage(max_weight: int,
                         truck_num: int, buggage_list: List[int]) -> bool:
    i = 0
    truck = [0 for i in range(truck_num + 1)]
    for buggage in buggage_list:
        if truck[i] + buggage <= max_weight:
            truck[i] += buggage
        else:
            i += 1
            truck[i] += buggage
        if i > (truck_num - 1):
            return False
    for t in truck:
        if t > max_weight:
            return False
    else:
        return True


# data = [i for i in range(31)]
# for d in data:
#     result = able_to_load_buggage(d, truck_num, buggage_list)
#     print(f'{d} {result}')

left = 0
right = 100000 * 10000 + 1
i = 0
while left < right:
    i += 1
    mid = math.floor((left + right) / 2)
    result = able_to_load_buggage(mid, truck_num, buggage_list)
    # print(f'{i} {left} {mid} {right} {result}')
    if result:
        right = mid
    else:
        left = mid + 1
# print(f'{left} {mid} {right}')
print(left)

Submission status: Accepted

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


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


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


T = []
for _ in range(n):
    T.append(int(input()))
ans = solve()
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math, sys

def loadable(w, n, k, p, wsum):
    wait = 0
    for i in range(n):
        wait += w[i]
        wsum -= w[i]
        if wait > p:
            k -= 1
            wait = w[i]
            if k == 0 or p < wsum / k:
                return False
    return True

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

wsum = sum(w)

p = max(int(math.ceil(wsum / k)), max(w))
pre_f = p -1
pre_s = None

while True:
    if loadable(w, n, k, p, wsum):
        pre_s = p
    else:
        pre_f = p

    if pre_s != None and pre_s - pre_f == 1:
            break
    
    if pre_s:
        p = int((pre_s + pre_f) / 2)
    else:
        p = math.ceil(p * 1.01)
    
print(pre_s)

Submission status: Accepted

Solution code:
n, _k = map(int, raw_input().split())
w = [int(raw_input()) for i in xrange(n)]

l, r = max(w), sum(w)
while r > l:
    P = (r + l) / 2
    c = P
    k = _k - 1
    for wi in w:
        if c >= wi: c -= wi
        else:
            c = P - wi
            k -= 1
            if k < 0:
                break
    if k >= 0:
        r = P
    else:
        l = P + 1
print l

Submission status: Accepted

Solution code:
n, k = [ int( val ) for val in raw_input( ).split( " " ) ]
w = []
maxW = sumW = 0
for i in range( n ):
	num = int( raw_input( ) )
	sumW += num
	w.append( num )
	if maxW < num:
		maxW = num

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

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

print( minP )

Submission status: Accepted

Solution code:
n, k = [ int( val ) for val in input( ).split( " " ) ]
w = []
maxW = sumW = 0
for i in range( n ):
	num = int( input( ) )
	sumW += num
	w.append( num )
	if maxW < num:
		maxW = num

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

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

print( minP )