Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

  You are given $n$ packages of $w_i$ kg from a belt conveyor in order ($i = 0, 1, ... n-1$). You should load all packages onto $k$ trucks which have the common maximum load $P$. Each truck can load consecutive packages (more than or equals to zero) from the belt conveyor unless the total weights of the packages in the sequence does not exceed the maximum load $P$. 

  Write a program which reads $n$, $k$ and $w_i$, and reports the minimum value of the maximum load $P$ to load all packages from the belt conveyor.

Input

  In the first line, two integers $n$ and $k$ are given separated by a space character. In the following $n$ lines, $w_i$ are given respectively.

Output

  Print the minimum value of $P$ in a line.

Constraints

 $1 \leq n \leq 100,000$

 $1 \leq k \leq 100,000$

 $1 \leq w_i \leq 10,000$

Sample Input 1

5 3
8
1
7
3
9

Sample Output 1

10

    If the first truck loads two packages of $\{8, 1\}$, the second truck loads two packages of $\{7, 3\}$ and the third truck loads a package of $\{9\}$, then the minimum value of the maximum load $P$ shall be 10.

Sample Input 2

4 2
1
2
2
6

Sample Output 2

6

    If the first truck loads three packages of $\{1, 2, 2\}$ and the second truck loads a package of $\{6\}$, then the minimum value of the maximum load $P$ shall be 6.



Sample input:
5 3
8
1
7
3
9


Sample output:
10

Submission status: Accepted

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

def bs(left, right):
    mid = 0
    
    while left < right:
        mid = (left + right ) //2
        if check(mid, w, k):
            right = mid
        else:
            mid += 1
            left = mid
    return mid

def check(v, wgt, num):
    cnt = 1
    tmp = 0
    for j in wgt:
        tmp += j
        if tmp > v:
            tmp = j
            cnt += 1
            if cnt > num:
                return False
    return True
    
print(bs(max(w), sum(w)))

Submission status: Accepted

Solution code:
#coding:UTF-8
def Check(P,k,w):
    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 Allocation(n,k,w):
    left=0
    right=100000000000000
    while right-left > 1:
        mid=int((left+right)/2)
        v=Check(mid,k,w)
        if v>=n:
            right=mid
        else:
            left=mid
    print(right)
  
if __name__=="__main__":
    a=input()
    n=int(a.split(" ")[0])
    k=int(a.split(" ")[1])
    w=[]
    for i in range(n):
        w.append(int(input()))
    Allocation(n,k,w)

Submission status: Accepted

Solution code:
# encoding: utf-8


import sys


class Solution:
    def __init__(self):
        """
        init input array
        """
        self.__input = sys.stdin.readlines()

    @property
    def solution(self):
        product_num = int(self.__input[0].split()[0])
        truck_num = int(self.__input[0].split()[1])
        weight_list = list(map(int, self.__input[1:]))

        assert product_num == len(weight_list)

        # binary search
        left, right, mid = max(weight_list), sum(weight_list), 0
        while left < right:
            mid = (left + right) // 2
            # check return True : p could be smaller
            if self.check(mid, weight_list, truck_num):
                right = mid
            else:
                mid += 1
                left = mid
        return str(mid)

    @staticmethod
    def check(max_load_cursor, weight_list, truck_num):
        track_count = 1
        current_load = 0
        for item_weight in weight_list:
            current_load += item_weight
            # change to next truck
            if current_load > max_load_cursor:
                current_load = item_weight
                track_count += 1
                if track_count > truck_num:
                    return False
        return True


if __name__ == '__main__':
    case = Solution()
    print(case.solution)

Submission status: Accepted

Solution code:
# encoding: utf-8


import sys


class Solution:
    def __init__(self):
        """
        init input array
        """
        self.__input = sys.stdin.readlines()

    @property
    def solution(self):
        product_num = int(self.__input[0].split()[0])
        truck_num = int(self.__input[0].split()[1])
        weight_list = list(map(int, self.__input[1:]))

        # assert product_num == len(weight_list)

        # binary search
        left, right, mid = max(weight_list), sum(weight_list), 0
        while left < right:
            mid = (left + right) // 2
            # check return True : p could be smaller
            if self.check(max_load_cursor=mid, weight_list=weight_list, truck_num=truck_num):
                right = mid
            else:
                mid += 1
                left = mid
        return str(mid)

    @staticmethod
    def check(max_load_cursor, weight_list, truck_num):
        track_count = 1
        current_load = 0
        for item_weight in weight_list:
            current_load += item_weight
            # change to next truck
            if current_load > max_load_cursor:
                current_load = item_weight
                track_count += 1
                if track_count > truck_num:
                    return False
        return True


if __name__ == '__main__':
    case = Solution()
    print(case.solution)

Submission status: Accepted

Solution code:
def calc_k(p, ws):
    k = 1
    s = 0
    for w in ws:
        if w > p:
            return None
        elif s + w <= p:
            s += w
        else:
            k += 1
            s = w
    return k

def search_minimum_p(k, ws):
    """
    ?????????P????????????????????¢?´¢??????
    max(P) = max(wi) * max(n)
    ????????¨???????????????1??°?????¨????????????????????????
    min(P) = max(wi)
    ?°?????????¨??????????????????????????§????????????????????????????????????
    """
    lp = max(ws)
    rp = 10000 * 100000

    while lp <= rp:
        cp = (lp + rp) // 2
        k1 = calc_k(cp, ws)
        if k1 <= k:
            # ???????????¨???????????????k??°??\????????????????????§??????
            k2 = calc_k(cp - 1, ws)
            if k2 == None or k2 > k:
                # cp???k??°???????????????????????????p???????°??????§??????
                return cp
            else:
                # ???????°???????p????????¨??????
                rp = cp - 1
        else:
            # ???????????¨???????????????k??°????????????????????????????????????????????????????¶?????????????
            lp = cp + 1

    return None

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

print(search_minimum_p(k, ws))

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
ww = [int(input()) for _ in range(n)]
def chk(p):
    c = 1
    s = 0
    for w in ww:
        if w > p:
            return False
        if s + w <= p:
            s += w
        else:
            c += 1
            s = w
        if c > k:
            return False
    return True
def search(l, r):
    if r - l < 10:
        for i in range(l, r):
            if chk(i):
                return i
    m = (l + r) // 2
    if chk(m):
        return search(l, m + 1)
    else:
        return search(m, r)
print(search(0, 2 ** 30))

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
ww = [int(input()) for _ in range(n)]
def chk(p):
    c = 1
    s = 0
    for w in ww:
        if w > p:
            return False
        if s + w <= p:
            s += w
        else:
            c += 1
            s = w
        if c > k:
            return False
    return True
def search(l, r):
    if r - l < 10:
        for i in range(l, r):
            if chk(i):
                return i
    m = (l + r) // 2
    if chk(m):
        return search(l, m + 1)
    else:
        return search(m + 1, r)
print(search(0, 2 ** 30))

Submission status: Accepted

Solution code:
#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_D
#??????????????????

def cal(truck_num, cargos):
    p = 0
    
    for i in range(len(cargos) - truck_num + 1):
        if not i == 0 and p < sum(cargos[:i + 1]):
            continue
        if truck_num > 1:
            r = max(sum(cargos[:i + 1]), cal(truck_num - 1, cargos[i + 1:]))
            if i == 0:
                p = r
            elif p > r:
                p = r
        else:
            return sum(cargos)
    return p

def check(truck_num, carogs, target_load):
    
    cur_truck = 1
    cur_weight = 0
    for weight in cargos:
        cur_weight += weight
        if cur_weight > target_load:
            cur_weight = weight
            cur_truck += 1
            if cur_truck > truck_num:
                return False
    return True

def solve(truck_num, cargs):

    max_load = sum(cargos)
    min_load = max(cargos)
    #print(min_load, max_load)
    while min_load < max_load:
        target_load = int((min_load + max_load)/2)
        if check(truck_num, cargos, target_load):
            max_load = target_load
        else:
            min_load = target_load + 1
        #print(min_load, max_load)
        
    return max_load

if __name__ == "__main__":
    line = input()
    truck_num = int(line.split(" ")[1])
    line_num = int(line.split(" ")[0])
    cargos = [int(input()) for i in range(line_num)]
    print(solve(truck_num,cargos))

Submission status: Accepted

Solution code:


global N,K
global ws

def check(max_p):
    track=0
    now=0
    for i in range (N):
        if(ws[i]>max_p):return False
        if(now+ws[i]>max_p):
            track+=1
            now=ws[i]
        else:
            now+=ws[i]
    if now>0:
        track+=1
    if(track>K):
        return False
    else:
        return True

N,K=map(int,input().split())

ans=0
now=0
ws=[]
for i in range(N):
    w=int(input())
    ws.append(w)

amin=0
amax=int(1E20)

while amin+1!=amax:
    amid=(amin+amax)//2
    if(check(amid)):
        amax=amid
    else:
        amin=amid
print(amax)

Submission status: Accepted

Solution code:


global N,K
global ws

def check(max_p):
    track=0
    now=0
    for i in range (N):
        if(ws[i]>max_p):return False
        if(now+ws[i]>max_p):
            track+=1
            now=ws[i]
        else:
            now+=ws[i]
    if now>0:
        track+=1
    if(track>K):
        return False
    else:
        return True

N,K=map(int,input().split())

ans=0
now=0
ws=[]
for i in range(N):
    w=int(input())
    ws.append(w)

amin=0
amax=int(1E30)

while amin+1!=amax:
    amid=(amin+amax)//2
    if(check(amid)):
        amax=amid
    else:
        amin=amid
print(amax)

Submission status: Accepted

Solution code:


global N,K
global ws

def check(max_p):
    track=0
    now=0
    for i in range (N):
        if(ws[i]>max_p):return False
        if(now+ws[i]>max_p):
            track+=1
            now=ws[i]
        else:
            now+=ws[i]
    if now>0:
        track+=1
    if(track>K):
        return False
    else:
        return True

N,K=map(int,input().split())

ans=0
now=0
ws=[]
for i in range(N):
    w=int(input())
    ws.append(w)

amin=0
amax=int(1E48)

while amin+1!=amax:
    amid=(amin+amax)//2
    if(check(amid)):
        amax=amid
    else:
        amin=amid
print(amax)

Submission status: Accepted

Solution code:
def calc_allocatable_packet(packets, num_of_trucks, p_max):
    """ ?????????????????°?????????????????§?????????????±?????????????n??°??????????????????????????????????????°????±??????? """
    num_of_packets = len(packets)
    next_p = 0  # ?????°?????????????????° ??? ?¬????packet[i]?????????????????????
    for t in range(num_of_trucks):
        payload = 0  # ??????????????????????????????
        while next_p < num_of_packets:
            if payload + packets[next_p] <= p_max:  # ?¬?????????????????????§???????
                payload += packets[next_p]
                next_p += 1
            else:
                break  # ?¬???????????????????
    return next_p


def calc_minimum_payload(packets, num_of_trucks):
    num_of_packets = len(packets)
    lower_limit = packets[0]
    upper_limit = 10000 * num_of_packets

    while lower_limit < upper_limit:
        middle = (lower_limit + upper_limit) // 2
        result = calc_allocatable_packet(packets, num_of_trucks, middle)
        if result < num_of_packets:
            lower_limit = middle + 1
        else:
            upper_limit = middle

    return lower_limit


if __name__ == '__main__':
    # ??????????????\???
    num_of_packets, num_of_trucks = [int(x) for x in input().split(' ')]
    packets = [int(input()) for _ in range(num_of_packets)]
    # num_of_packets, num_of_trucks = 0, 0
    # packets = []
    # with open('ALDS1_4_D_in25.txt') as f:
    #    for line in f:
    #       if ' ' not in line:
    #           packets.append(int(line))
    #       else:
    #           num_of_packets, num_of_trucks = [int(x) for x in line.split(' ')]



    # ???????????????
    result = calc_minimum_payload(packets, num_of_trucks)

    # ???????????¨???
    print(result)

Submission status: Accepted

Solution code:
# coding: utf-8

n, k = map(int, input().rstrip().split())
w = [0 for _ in range(n)]
for i in range(n):
    w[i] = int(input())
    
# from random import randint
# n = 100000
# k = 10000
# w = [0 for _ in range(n)]
# for i in range(n):
#     w[i] = randint(1, 10000)
# print(w)
count = 0

def check(P):
    m = 0
    ik = 1
    for i in range(n):
        global count
        count += 1
        new = m + w[i]
        if new > P:
            m = w[i]
            ik += 1
            if ik > k:
                return False
        else:
            m = new
    return True

s = max(sum(w)//k, max(w))
e = sum(w)

while True:
    P = (s + e)//2
    # print("s:{}, e:{}, P:{}".format(s, e, P))
    if s == e:
        break
    if check(P):
        e = P
    else:
        s = P + 1
            
        
print(P)
# print(count)

Submission status: Accepted

Solution code:
import sys

def check_sekisairyo(p_min):
    p_now = 0
    k_now = 0
    for w in w_i:
        p_now += w
        if p_now > p_min:
            p_now = w
            k_now += 1
        elif p_now == p_min:
            p_now = 0
            k_now += 1
        if k_now == k and p_now != 0:
            return False
    return True

n, k = map(int, input().split())
w_i = [int(input()) for i in range(n)]
left, right, p_min = max(w_i), sum(w_i), 0
while left < right:
    p_min = (left + right) // 2
    if check_sekisairyo(p_min):
        right = p_min
    else:
        left = p_min = p_min + 1
print(p_min)

Submission status: Accepted

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

    # print(max_p, min_p)
    # sys.exit(0)

    capable = {min_p:False, max_p:True}

    # sys.exit(0)
    
    bottom = min_p
    top = max_p

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

        if mid not in capable:
            capable[mid] = is_capable(n, k, w, mid)

        if capable[mid] == True:
            if (mid - 1) not in capable:
                capable[mid - 1] = is_capable(n, k, w, mid - 1)

            if capable[mid - 1] == False:
                ans = mid
                break
            else:
                top = mid
        elif capable[mid] == False:
            if (mid + 1) not in capable:
                capable[mid + 1] = is_capable(n, k, w, mid + 1)

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

    print(ans)
    # print(capable)

Submission status: Accepted

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 i

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

    return i
    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

    # print(max_p, min_p)
    # sys.exit(0)
    
    bottom = min_p
    top = max_p

    while top - bottom > 1:
        mid = (bottom + top) // 2

        if is_capable(n, k, w, mid) == n:
            top = mid
        else:
            bottom = mid

    print(top)

Submission status: Accepted

Solution code:
def check(p, k, arr):
  subtotal = 0
  num_of_tracks = 1
  for a in arr:
    subtotal += a
    if subtotal > p:
      num_of_tracks += 1
      if num_of_tracks > k: return False
      subtotal = a
  return True

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

min_p = max(arr)
max_p = sum(arr)
while min_p < max_p:
  mid_p = (min_p + max_p) // 2
  if check(mid_p, k, arr):
    max_p = mid_p
  else:
    min_p = mid_p + 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):
    c = t = 0
    for wi in w:
        t += wi
        if t > p:
            t = wi
            c += 1
            if c >= k:
                return False
    return True

s = max(w)
l = sum(w)
m = l + (s-l)*k//n
while s < l:
    if check(m):
        l = m
    else:
        s = m+1
    m = (s+l)//2
print(m)

Submission status: Accepted

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

def check(p):
    c = t = 0
    for wi in w:
        t += wi
        if t > p:
            t = wi
            c += 1
            if c >= k:
                return False
    return True

s = max(w)
l = sum(w)
while s < l:
    m = (s+l)//2
    if check(m):
        l = m
    else:
        s = m+1
print(s)

Submission status: Accepted

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

def check(p):
    c = t = 0
    for wi in w:
        t += wi
        if t > p:
            t = wi
            c += 1
            if c >= k:
                return False
    return True

s = max(w)
l = sum(w)
while s != l:
    m = (s+l)//2
    if check(m):
        l = m
    else:
        s = m = m+1
print(s)

Submission status: Accepted

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

def check(p):
    c = t = 0
    for wi in w:
        t += wi
        if t > p:
            t = wi
            c += 1
            if c >= k:
                return False
    return True

s = max(w)
l = sum(w)
while s < l:
    m = (s+l)//2
    if check(m):
        l = m
    else:
        s = m = m+1
print(s)

Submission status: Accepted

Solution code:
import sys
import math 

def be_able_to_convey(w, k, p):
	counter = 0
	cur_weight = 0
	for wi in w:
		if wi > p:
			return False

		cur_weight += wi
		if(cur_weight > p):
			cur_weight = wi
			counter += 1
			if(counter >= k):
				return False

	return True

#fin = open("test.txt", "r")
fin = sys.stdin

n, k = map(int, fin.readline().split())
w = [0 for i in range(n)]

for i in range(n):
	w[i] = int(fin.readline())
	
pmin = 1
pmax = int(10e9)

while pmin < pmax:
	p = math.ceil((pmin + pmax) / 2)
	if p == pmin or p == pmax:
		if be_able_to_convey(w, k, pmin):
			p = pmin
		else:
			#if not be_able_to_convey(w, k, pmax):
			#	print("error")
			p = pmax
		break

	if not be_able_to_convey(w, k, p):
		pmin = p
	else:
		pmax = p

print(p)

Submission status: Accepted

Solution code:
import sys
n,k = map(int,input().split())
w = list(map(int,sys.stdin.readlines()))

def binarysearch(start,end):
    left = start
    right = end
    middle = 0
    while left < right:
        middle = (left + right)//2
        if simulate(middle,w,k):
            right = middle
        else:
            left = middle + 1
    return left

def simulate(prb,wei,dai):
    count = 1
    tmp = 0
    for j in wei:
        tmp += j
        if tmp > prb:
            tmp = j
            count += 1
            if count > dai:
                return False
    return True

print(binarysearch(max(w), sum(w)))

Submission status: Accepted

Solution code:
import sys

def binarySearch(t,w):
    left = max(w)
    right = sum(w)
    while left < right:
        middle = (left + right) // 2
        if hantei(t,w,middle):
            right = middle 
        else:
            left = middle + 1
    return left
            
def hantei(t,w,p):
    track_on = 0
    daisu = 1
    for j in range(len(w)):     
        track_on += w[j]
        if track_on > p:
            daisu += 1
            track_on = w[j]
            if daisu > t:
                return False
    return True


nimotsu, track = map(int,input().split())
weight = list(map(int,sys.stdin.readlines()))



print(binarySearch(track,weight))

Submission status: Accepted

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


def check_numbers(cargo_weight_list, number_of_all_cargo, number_of_tracks, maximum_weight):
    """check the numbers that are loadable in tracks
    
    Args:
        cargo_weight_list: cargo weight list
        number_of_tracks: the number of tracks
        
    Returns:
        the number of cargos that are loadable in tracks
    """
    counter = 0
    number_of_loaded_cargo = 0

    while counter < number_of_tracks:
        current_track_weight = 0

        while current_track_weight + cargo_weight_list[number_of_loaded_cargo] <= maximum_weight:
            current_track_weight += cargo_weight_list[number_of_loaded_cargo]
            number_of_loaded_cargo += 1
            if number_of_loaded_cargo == number_of_all_cargo:
                return number_of_all_cargo

        counter += 1

    return number_of_loaded_cargo


def find_the_minimum_of_maximum_weihgt(cargo_weight_list, number_of_all_cargo, number_of_tracks):
    """find the minimum of maximum weight s.t all of the cargos can be loaded into tracks.
    (binary search is used. the number of loadable cargos monotonicaly increases as the maximum weight increases)


    Args:
        cargo_weight_list: cargo weight list
        numbef of all cargo: the number of all cargos
        number of tracks: the number of tracks

    Returns:
        minumim number of maximum track weight that are needed to load all of the cargos
    """
    left = max(cargo_weight_list)
    right = sum(cargo_weight_list)
    while (right - left) > 0:
        middle = (right + left) / 2
        the_number_of_loadable_cagos = check_numbers(cargo_weight_list, number_of_all_cargo, number_of_tracks, middle)
        if the_number_of_loadable_cagos >= number_of_all_cargo:
            right = middle
        else:
            left = middle + 1

    return right

def main():
    number_of_all_cargo, number_of_tracks = [int(x) for x in raw_input().split(' ')]
    cargo_weight_list = [int(raw_input()) for _ in xrange(number_of_all_cargo)]
    
    print find_the_minimum_of_maximum_weihgt(cargo_weight_list, number_of_all_cargo, number_of_tracks)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

import sys
import os


n, k = map(int, input().split())
#print(k, '??°??§????????????')

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

def check(P):
    # ?????????P?????\?????¨??????????????????????????????????????????????????¢??°
    weight_index = 0
    for i in range(k):
        current_weight = 0
        while current_weight + W[weight_index] <= P:
            #print('i', i, W[weight_index], '?????????')
            current_weight += W[weight_index]
            weight_index += 1
            if weight_index == len(W):
                # ??¨??¨?????£???
                return len(W)
    return weight_index

P_min = 1
P_max = 100000 * 10000
P_mid = None
while True:
    P_mid = (P_min + P_max) // 2
    loaded_num = check(P_mid)

    if loaded_num < n:
        # ????????????????????????
        P_min = P_mid
    else:
        # ??????????????????????????§???P??????????????¢???
        P_max = P_mid

    if P_max - P_min <= 1:
        break

# ??????
if check(P_min) == n:
    print(P_min)
else:
    print(P_max)

Submission status: Accepted

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

import sys
import os


n, k = map(int, input().split())
#print(k, '??°??§????????????')

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

def check(P):
    # ?????????P?????\?????¨??????????????????????????????????????????????????¢??°
    weight_index = 0
    for i in range(k):
        current_weight = 0
        while current_weight + W[weight_index] <= P:
            #print('i', i, W[weight_index], '?????????')
            current_weight += W[weight_index]
            weight_index += 1
            if weight_index == len(W):
                # ??¨??¨?????£???
                return len(W)
    return weight_index

P_min = 1
P_max = sum(W)
P_mid = None
while True:
    P_mid = (P_min + P_max) // 2
    loaded_num = check(P_mid)

    if loaded_num < n:
        # ????????????????????????
        P_min = P_mid
    else:
        # ??????????????????????????§???P??????????????¢???
        P_max = P_mid

    if P_max - P_min <= 1:
        break

# ??????
if check(P_min) == n:
    print(P_min)
else:
    print(P_max)

Submission status: Accepted

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

import sys
import os


n, k = map(int, input().split())
#print(k, '??°??§????????????')

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

def check(P):
    # ?????????P?????\?????¨??????????????????????????????????????????????????¢??°
    weight_index = 0
    for i in range(k):
        current_weight = 0
        while current_weight + W[weight_index] <= P:
            #print('i', i, W[weight_index], '?????????')
            current_weight += W[weight_index]
            weight_index += 1
            if weight_index == len(W):
                # ??¨??¨?????£???
                return len(W)
    return weight_index

P_min = 1
P_max = sum(W)
P_mid = None
while True:
    P_mid = (P_min + P_max) // 2
    loaded_num = check(P_mid)

    if loaded_num < n:
        # ????????????????????????
        P_min = P_mid + 1
    else:
        # ??????????????????????????§???P??????????????¢???
        P_max = P_mid

    if P_max == P_min:
        break

# ??????
print(P_max)

Submission status: Accepted

Solution code:
def check(k, p, w_list):
    i_w = 0
    for i_k in range(k):
        sum_w = 0
        while True:
            if i_w >= len(w_list):
                return len(w_list)
            if sum_w + w_list[i_w] > p:
                break
            sum_w += w_list[i_w]
            i_w += 1
    return i_w

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

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

left = 0
right = 100000 * 10000
mid = None

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

print(right)

Submission status: Accepted

Solution code:
def allocation():
    n, cars = map(int, input().split())
    weight = [int(input()) for i in range(n)]

    left = max(weight)
    right = sum(weight)

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

        if check(weight, cars, mid):
            right = mid
        else:
            left = mid + 1

    print(left)

def check(weight, cars, capacity):
    t = 0
    c = 1
    for w in weight:
        t += w
        if t > capacity:
            t = w
            c += 1

    if c <= cars:
        return True
    else:
        return False

if __name__ == '__main__':
    allocation()

Submission status: Accepted

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


#P????????°??¨??????????????¬??§??????Wi????????°?????????????????¢??°
def howmany(P):
 ans = 0
 truck = 1
 i = 0
 while truck <= k and i <= n-1:
  rp = P
  while rp >= WL[i]:
   ans += 1
   rp -= WL[i]
   i += 1
   if i == n: break
  truck += 1
 return ans

low = 0
high = 100000 * 100000 # n * k????????§???
while low != high:
 mid = (low + high) // 2
 if howmany(mid) == n:
  high = mid
 else:
  low = mid + 1
print(str(low))

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding:utf-8 -*-

load_num, track_num = list(map(int, input().split(" ")))

loads = list()
for _ in range(load_num):
    loads.append(int(input()))

P = 10000 * 100000

def isMeet(p):
    i = 0

    for _ in range(track_num): # ??????????????°??°???????????????
        sum = 0 # ???????????????????????????
        while (sum + loads[i] <= p):
            sum += loads[i]
            i += 1
            if i == load_num:
                return True
    return False


def binary_search(P):
    left = 0 
    right = P
    while right - left > 0:
        mid = int((left+right)/2)
        if isMeet(mid):
            right = mid
        else:
            left = mid + 1
    return right

print(binary_search(P))

Submission status: Accepted

Solution code:
import math
n, k = map(int, input().split())
a = [int(input()) for _ in [None]*n]

lb = max(a)
ub = lb * n

while True:
    mid = (ub+lb) // 2
    remain = k - 1
    cw = 0
    for w in a:
        cw += w
        if cw > mid:
            remain -= 1
            cw = w
        if remain < 0:
            break
    if remain < 0:
        if lb == mid:
            print(lb+1)
            break
        lb = mid
    else:
        if lb == mid:
            print(lb)
            break
        ub = mid

Submission status: Accepted

Solution code:
import sys

global n, k, T


def cal_v(P):
    j = 0
    for i in range(k):
        con = 0
        while con + T[j] <= P:
            con += T[j]
            j += 1
            if j == n:
                return n
    return j


def cal_ans():
    left = 0
    right = sum(T)
    mid = (right-left) // 2
    while right - left > 1:
        mid = left + (right-left)//2
        if cal_v(mid) >= n:
            right = mid
        else:
            left = mid
    return right

if __name__ == "__main__":
    n, k = map(int, sys.stdin.readline().split())
    T = list(map(int, sys.stdin.readlines()))
    ans = cal_ans()
    print(ans)

Submission status: Accepted

Solution code:
def check(P,w,n):
    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

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

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