Problem:


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

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

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

Input

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

Output

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

Constraints

 $1 \leq n \leq 100,000$

 $1 \leq k \leq 100,000$

 $1 \leq w_i \leq 10,000$

Sample Input 1

5 3
8
1
7
3
9

Sample Output 1

10

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

Sample Input 2

4 2
1
2
2
6

Sample Output 2

6

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



Sample input:
5 3
8
1
7
3
9


Sample output:
10

Submission status: Accepted

Solution code:
import math
import collections
n, k = map(int, input().split())
W = collections.deque()
for i in range(n):
    W.append(int(input()))
left = max(math.ceil(sum(W) / k), max(W))
right = sum(W)
center = (left + right) // 2
# print('------')
while left < right:
    i = 1
    track = 0
    # print(center)
    for w in W:
        # if center == 26:
        #     print('track: ' + str(track))
        track += w
        if track > center:
            track = w
            i += 1
            if i > k:
                left = center + 1
                break
    else:
        right = center
    center = (left + right) // 2
print(center)

Submission status: Accepted

Solution code:
#インプットdataの格納
n, k = map(int, input().split())
n_list = list()
for i in range(n):
    n_list.append(int(input()))

#data処理
left = 0
right = 100000*10000
while (right - left) > 1:
    mid = (left + right) // 2

    i = 0
    for j in range(k):
        weight = 0
        while i < n:
            if (weight + n_list[i]) > mid:
                break
            else:
                weight += n_list[i]
                i += 1

    if i >= n:
        right = mid
    else:
        left = mid
        
#結果表示
print(right)

Submission status: Accepted

Solution code:
import math
import string
import itertools
import fractions
import heapq
import collections
import re
import array
import bisect
import sys
import random
import time
inf = 10**9

n, k = [0, 0]
w = []


def validate(p):
    c = 0
    for i in range(k):
        s = 0
        while s + w[c] <= p:
            s = s + w[c]
            c = c + 1
            if c == n:
                return True
    return False


def main():
    global n
    global k
    global w
    n, k = map(int, input().split())
    for i in range(n):
        w.append(int(input()))

    # bianry search
    left = 0
    right = 100000 * 10000
    p = right / 2
    while left != right:
        if validate(p):
            right = p
        else:
            left = p + 1
        p = math.floor((left + right) / 2)

    print(p)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

p_max = 1000000 * 1000000
n, k = map(int, input().split())
w = [int(input()) for i in range(n)]

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

if __name__ == "__main__":
  right = p_max
  left = 0
  mid = 0
  while (right - left > 1):
    mid = math.floor((right + left) / 2)
    v = check(mid)
    if v >= n:
      right = mid
    else:
      left = mid
  
  print (right)

Submission status: Accepted

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

def num_luggage(P, K, lst):
    weight = 0
    n_track = 1
    for i, e in enumerate(lst):
        if (e > P):
            return i
        if (weight + e <= P):
            weight += e
        else:
            n_track += 1
            weight = e
        if (n_track == K+1):
            return i
    return len(lst)

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

print(right)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = [int(input()) for s in range(n)]
pmax = sum(a)
pmin = pmax//k-1

def check(ptest):
    tk = 1
    p = 0
    global a,k,n
    i = 0
    while i < n:
        p += a[i]
        if p <= ptest:
            i += 1
        else:
            tk += 1
            p = 0
        if tk > k:
            return False
    return True

while (pmax-pmin) > 1:
    pmid = (pmax+pmin)//2
    if check(pmid):
        pmax = pmid
    else:
        pmin = pmid
print(pmax)

Submission status: Accepted

Solution code:
def p_is_smaller(p):
    total = 0
    number_of_track = 1
    for w in W:
        total += w
        if total > p:
            number_of_track += 1
            if number_of_track > k:
                return 1
            total = w
    return 0

if __name__ == "__main__":
    n, k = map(int, input().split())
    W = [int(input()) for _ in range(n)]
    left, right = max(W), sum(W)
    while right > left:
        mid = (left + right) // 2
        if p_is_smaller(mid):
            left = mid + 1
        else:
            right = mid
    print(right)

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
W = []
for _ in range(N):
  W.append(int(input()))
    
def carriable(p):
  if p < max(W):
    return False
  
  k_count = 0
  current_weight = 0
  for w in W:
    if current_weight + w <= p:
      current_weight += w
    else:
      if k_count + 1 < K:
        k_count += 1
        current_weight = w
      else:
        return False
      
  return True

def solve():
  min_p = 0
  max_p = sum(W)
  current_p = (max_p + min_p) // 2
  
  while True:    
    if min_p == current_p:
      return max_p
    
    if carriable(current_p):
      max_p = current_p
    else:
      min_p = current_p
    current_p = (max_p + min_p) // 2
    
print(solve())

Submission status: Accepted

Solution code:
# 17D8103013C miukou42 python3

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

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

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

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

Submission status: Accepted

Solution code:
import sys
n, k = map(int, input().split())
T = [int(input()) for i in range(n)]
def c(mid):
	global k,T,n
	i=0
	for j in range(k):
		s=0
		while s+T[i]<=mid:
			s+=T[i]
			i+=1
			if(i == n):
				return n
	return i
def Allocation():
	l=0
	r=sys.maxsize
	while r-l>1:
		mid=(l+r)//2
		v=c(mid)
		if (v>=n):
			r=mid
		else:
			l=mid
	return r
x=Allocation()
print(x)

Submission status: Accepted

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

Submission status: Accepted

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

def check(P):
    global k, T, n

    i = 0
    for j in range(k):
        s = 0
        while s + T[i] <= P:
            s += T[i]
            i += 1
            if (i == n):
                return n
	
    return i
def find():
    
    left = 0
    right = 100000 * 10000

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

    return right


print(find())

Submission status: Accepted

Solution code:
n, k = (int(x) for x in input().split())

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

def f(x):
    count = 0
    for i in range(k):
        s = 0
        while s + w[count] <= x:
            s += w[count]
            count += 1
            if count == n:
                return n
    return count

left = 0
right = 100000 * 100000

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

print(right)

Submission status: Accepted

Solution code:
def chkp(P):
    global n, 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 binary_search():
    l = 0
    r = 100000 * 10000
    while r - l > 1:
        c = (l+r) // 2
        v =  chkp(c)
        if(v >= n):
            r = c
        else:
            l = c
    return r

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

Submission status: Accepted

Solution code:
def main():
    def check(p):
        # 積めた荷物の数
        i = 0
        # トラックの数だけ試行
        for _ in range(k):
            # 現在のトラックの重量
            s = 0
            while s + w[i] <= p:
                # 積める場合は積んで次の荷物へ
                # 積めない場合は次のトラックへ
                s += w[i]
                i += 1
                if i == n:
                    return n
        return i

    def solve():
        left, right = 0, 100000 * 10000 + 1
        while left < right:
            mid = (left + right) // 2
            if n <= check(mid):
                right = mid
            else:
                left = mid + 1
        return left

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

for i in range(N):
    W.append(int(input()))

def f(N, K, W, p):
    cnt = 0
    k = 1
    c_k = 0
    for w in W:
        if c_k + w <= p:
            c_k = c_k + w
            cnt = cnt + 1
        elif k < K and w <= p:
            k = k + 1
            c_k = w
            cnt = cnt + 1
        elif k < K and w > p:
            pass
        else:
            break
    return cnt

start = 0
end = 1000000000
while start != end:
    center = (start + end)//2
    if f(N, K, W, center) < N:
        start = center + 1
    else:
        end = center

print(start)

Submission status: Accepted

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


def check(P): # 最駄積載量Pのk台のトラックで何個目の荷物まで積めるか。積める荷物の数をreturn
    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

# 今、条件より1<=w<=10,000であり、1<=n<=100000
# つまり、トラックの最大積載量の取りうる最大値はこれらが一つのトラックに乗る時、つまり100000*10000
# 従ってこの範囲でPを探索すればよい
# 二分探索を使うことができる（これらのmidをPと仮定してcheckで積める個数を調べる
#→これがnよりも大きければPはもっと小さくて良いと言うことなのでrightをmidに、小さければleftをmidに！

        
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

ans = math.floor(solve())
print(ans)

Submission status: Accepted

Solution code:
import sys

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

lower_p = 0
w_list = []
for _ in range(n):
    w = int(sys.stdin.readline())
    lower_p = w if w > lower_p else lower_p
    w_list.append(w)
    
def get_possible_n(p):
    """最大積載重量を p としたときに、所与のトラック台数 k で処理可能な荷物の数

    所与の荷物数 n のうち、いくつ処理可能かを返す。荷物の重量と順序に依存し、
    （弱い）単調増加関数である。これが返す最大値は n である。
    """
    pos_n = 0
    for _ in range(k):
        acc_w = 0
        while pos_n < n:
            if acc_w + w_list[pos_n] <= p:
                acc_w += w_list[pos_n]
                pos_n += 1
            else:
                break
        else:
            break
    return pos_n

# upper_p は、get_possible_n(upper_p) が確実に n を返すことが保証される値。
upper_p = lower_p * n // k + lower_p

def b_search(lower_p, upper_p):
    while lower_p < upper_p:
        mid_p = (lower_p + upper_p) // 2
        if get_possible_n(mid_p) < n:
            lower_p = mid_p + 1
        else:
            upper_p = mid_p
    return lower_p

print(b_search(lower_p, upper_p))

Submission status: Accepted

Solution code:
n, k  = map(int, input().split())
w = []
def check(ptest):
    tk=1
    p=0
    global k
    global w
    global n
    i=0
    
    while i<n:
        p+=w[i]
        if p<=ptest:
            i+=1
        else:
            tk+=1
            p=0
            
        if tk>k:
            return 0
            #break   
    
    return 1
for i in range(n):
    w.append(int(input()))
pmax = sum(w)
pmin = pmax//k - 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:
def check(P):
    global k,T,n
    
    i = 0
    for j in range(k):
        s = 0
        while s + T[i] <= P:
            s += T[i]
            i += 1
            if(i == n):
                return n
    return i
    
def solve():
    left = 0
    right = 100000 * 10000
    
    while right - left > 1:
        mid = (left + right)//2
        v = check(mid)
        if(v >= n):
            right = mid
        else:
            left = mid
    return right
    
if __name__ == '__main__':
    n,k = map(int,input().split())
    T = [int(input()) for i in range(n)]
    
    ans = solve()
    print(ans)

Submission status: Accepted

Solution code:
def check(list, p, k):
    i = 0
    for j in range(k):
        sum = 0
        while sum+list[i] <= p:
            sum += list[i]
            i += 1
            if i == len(list):
                return i


    return i

nk = list(map(int, input().split()))
n = nk[0]
k = nk[1]

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

max_num = 100000 * 10000

#二分探索で最大積載量の最小値を求める
left = 0
right = max_num
while left+1 < right:
    mid = int((left + right) /2)
    if check(list, mid, k) >= len(list):
        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 check(p):
    track = 0
    tmp_w = 0
    for i in range(N):
        if w[i] > p:
            return False
        else:
            if (tmp_w + w[i]) > p:
                track += 1
                tmp_w = w[i]
            else:
                tmp_w += w[i]
    if track + 1 > K:
        return False
    else:
        return True

left = 0
right = 2000000000
while((left + 1) < right):
    mid = (left + right) // 2
    track = check(mid)
    if check(mid):
        right = mid
    else:
        left = mid 
        
print(right)

Submission status: Accepted

Solution code:
def min_item_num(weights, num_item, num_vehicle, capacity):
    item_idx = 0
    for _ in range(num_vehicle):
        load = 0
        while load + weights[item_idx] <= capacity:
            load += weights[item_idx]
            item_idx += 1
            if item_idx == num_item:
                return num_item
    return item_idx


def main():
    num_item, num_vehicle = list(map(int, input().split(" ")))
    weights = [int(input()) for _ in range(num_item)]
    left = 0
    right = 10000 * 100000
    while right - left > 1:
        center = (left + right) // 2
        min_item = min_item_num(weights, num_item, num_vehicle, center)
        if num_item <= min_item:
            right = center
        else:  # min_vehicle > num_item:
            left = center
    print(right)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
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, right = 0, 100000*10000
    while right - left > 1:
        mid = (left + right) / 2
        v = check(mid)
        if v >= n: right = mid
        else: left = mid
    return right

if __name__ == '__main__':
    T = []
    n, k = [int(x) for x in input().split()]
    for i in range(n): T.append(int(input()))    
    print(int(solve()))

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!


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
    mid = 0
    while right - left > 1:
        mid = (left + right) // 2
        v = check(mid)
        if v >= n:
            right = mid
        else:
            left = mid
    return right
    
tmp = list(map(int, input().split())) 
n = tmp[0]
k = tmp[1]
T = []
for i in range(n):
    T.append(int(input()))
ans = solve()
print(ans)

Submission status: Accepted

Solution code:
n, k, *W = map(int, open(0).read().split())
left, right = 1000000000, max(W) - 1


def check(M):
    L = [W[0]]
    for i in range(1, n):
        if L[-1] + W[i] <= M:
            L[-1] += W[i]
        else:
            L.append(W[i])
    return len(L) <= k


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

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
l=0
r=10**9+1
ww=[]
for i in range(n):
	ww.append(int(input()))
while l<r:
	mid=(r+l)//2
	cnt=0
	tr=1
	for i in range(n):
		w=ww[i]
		if w>mid or tr>k:
			tr=10**18
			l=mid+1
			break
		if w+cnt<=mid:
			cnt+=w
		else:
			cnt=w
			tr+=1
	if tr<=k:
		r=mid
	else:
		l=mid+1
print(l)

Submission status: Accepted

Solution code:
import sys
def slove(goods, carnum, P):
    tot_good = len(goods)
    cur_good = 0
    for _ in range(carnum):
        load = 0
        while cur_good < tot_good and goods[cur_good] <= P -load:
            load += goods[cur_good]
            cur_good += 1
    if cur_good == tot_good:
        return True
    else:
        return False

if __name__ == '__main__':

    datas = input().split(' ')
    good_num = int(datas[0])
    car_num = int(datas[1])
    goods = []
    for _ in range(good_num):
        goods.append(int(input()))

    left = 0
    right = sys.maxsize
    while left < right:
        mid = (left + right) // 2
        if slove(goods, car_num, mid):
            # 当前的P较大
            right = mid
        else:
            left = mid + 1
    print(right)

Submission status: Accepted

Solution code:
#import pysnooper
#import numpy
#import os,re,sys,operator
from collections import Counter,deque
#from operator import itemgetter
#from itertools import accumulate,combinations,groupby,combinations_with_replacement,permutations
from sys import stdin,setrecursionlimit
#from bisect import bisect_left
#from copy import deepcopy
#import heapq
#import math
#import string
#from time import time
#from functools import lru_cache
setrecursionlimit(10**6)
input=stdin.readline

n,k=map(int,input().split())
w=[int(input().rstrip()) for _ in range(n)]
l,r=0,10**9
while l<r:
    m=(l+r)//2
    loop=0
    ch=False
    for i in range(k):
        noww=0
        while loop<n:
            if noww+w[loop]<=m:
                noww+=w[loop]
                loop+=1
            else: break
        else:
            ch=True
    if ch: r=m
    else: l=m+1
    #print(m,l,r)
print(l)

Submission status: Accepted

Solution code:
#coding: utf-8
n, k = map(int, input().split())
pkt = list()
for i in range(n):
    pkt.append(int(input()))
lenpkt = len(pkt)

def maxPkt(payload):
    maxPnum = 0
    for i in range(k):
        tempPL = 0
        while tempPL + pkt[maxPnum] <= payload:
            tempPL += pkt[maxPnum]
            maxPnum += 1
            if maxPnum == lenpkt:
                return True
    return False

lft = 0
mid = 0
rgt = 100000 * 10000

while lft < rgt:
    mid = (lft + rgt) // 2
    if maxPkt(mid):
        rgt = mid
    else:
        lft = mid + 1

print(rgt)

Submission status: Accepted

Solution code:
def track_number_needed(p, n_track):
    global W
    n_luggage = 0
    for j in range(n_track):
        weight_sum = 0
        while (weight_sum + W[n_luggage] <= p):
            weight_sum += W[n_luggage]
            n_luggage += 1
            if n_luggage == len(W):
                return n
    return n_luggage


def binary_search():
    global n
    global k
    left = 0
    right = 100000 * 10000
    while(right - left > 1):
        mid = (left + right) // 2
        n_luggage = track_number_needed(mid, k)
        if n_luggage >= n:
            right = mid
        else:
            left = mid
    return right
            


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

Submission status: Accepted

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

total_weght = sum(w)

def check(p):
    track = [0 for i in range(k)]
    target = 0

    for i in range(k):
        while (track[i] + w[target]) <= p:
            track[i] += w[target]
            target += 1
            if target not in range(n):
                break
        if target not in range(n):
            break
    
    return(target)

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

    return(right)

if __name__ == "__main__":
    ans = solve(n)
    print(ans)

Submission status: Accepted

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

def hantei(w,a,k):
    tumu=a
    daime=1
    for ww in w:
        if ww<=tumu:
            tumu-=ww
        else:        
            tumu=a
            daime+=1
            if ww<=tumu:
                tumu-=ww
            else:
                return False
    if daime >k:
        return False
    else:
        return True


right= max(w)*n +1
left = min(w)

while left<right:
    mid  = (left+right)//2
    if hantei(w,mid,k):
        right=mid
    else:
        left=mid+1
print(left)

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; cur = 0
    for w in W:
        if mid < cur + w:
            cur = w
            cnt += 1
        else:
            cur += w
    if cnt <= k:
        right = mid
    else:
        left = mid
print(right)

Submission status: Accepted

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

def main():
	n, k = map(int,input().split())
	w = []
	for _ in range(n):
		w += [int(input())]
	pmin = 0
	pmax = 10**10
	while True:
		if pmin >= pmax:
			print(pmin)
			break
		if check(int((pmin+pmax)/2),n,w,k):
			pmax = int((pmin+pmax)/2)
		else:
			pmin = int((pmin+pmax)/2)+1

main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
wList = []
for i in range(n):
    w = int(input())
    wList.append(w)
minP = max(wList)-1
maxP = sum(wList)
def countD(mid, wList):
    curr = 0
    count = 0
    for w in wList:
        if curr+w > mid:
            count+=1
            curr = w
        else:
            curr+=w
    if curr > 0:
        count+=1
    return count
while maxP - minP > 1:
    mid = (minP + maxP)//2
    days = countD(mid, wList)
    if days <= k:
        maxP = mid
    else:
        minP = mid
print(maxP)

Submission status: Accepted

Solution code:
# def f(P):
#     """与えられたPのときに、運べる荷物の数vを返す関数"""
#     i = 0  # 荷物の番号
#     v = 0  # 運べる荷物の数
#     k = 0  # トラックの番号
#     current_weight = 0  # 現在のトラックの重さ
#     # current_v = 0  # 現在のトラックに積まれている荷物の数
#
#     while True:
#         # print(i, v, k)
#
#         if W[i] > P:
#             i += 1
#         else:
#             current_weight += W[i]
#
#             if current_weight > P:
#                 k += 1
#             elif current_weight == P:
#                 i += 1
#                 v += 1
#                 k += 1
#             else:  # current_weight < P:
#                 i += 1
#                 v += 1
#
#         if i == N or k == K:
#             break
#     return v

def f(P):
    i = 0
    for k in range(K):
        current_weight = 0
        while current_weight + W[i] <= P:
            current_weight += W[i]
            i += 1
            if i == N:
                return N

    return i


def solve_binary():
    left = 0
    right = max(W)  # ではない！これだとトラックが足りなくて積み切れない場合がある。
    right = 100000 * 10000

    while (right - left) > 1:  # つまり、これが境目の証！！！
        mid = (left + right) // 2
        mid_v = f(mid)

        if mid_v >= N:
            right = mid
        elif mid_v < N:
            left = mid

    return right


def solve_linear():
    p = 1
    while True:
        v = f(p)
        # print(p, v, N)

        if v == N:
            # print(p)
            return p

        p = p + 1


N, K = map(int, input().split())
# W = list(map(int, input().split()))
W = [int(input()) for _ in range(N)]
# print(n, k, W)

# print(solve_linear())
print(solve_binary())

Submission status: Accepted

Solution code:
from collections import deque
def check(n, k, w_master, p):
    w = w_master.copy()
    for _ in range(k):
        weight_rem = p #残り積載可能重量
        while (len(w) > 0) and (weight_rem >= w[0]):
            weight_rem -= w.popleft()
    
        if len(w) == 0:
            return True

    return False

def main(n, k, w_master):
    amin=0
    amax= 10_000 *  100_000

    while amin+1!=amax:
        amid=(amin+amax)//2
        if(check(n, k, w_master, amid)):
            amax=amid
        else:
            amin=amid

    return amax 

if __name__ == "__main__":
    #input
    n, k = map(int, input().split())
    w_master = deque()
    for _ in range(n):
        w_master.append(int(input()))

    print(main(n, k, w_master))

Submission status: Accepted

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

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

left = 0
right = (10**5)*(10**4)
while right - left > 1:
    mid = (left+right)//2
    v = check(mid)
    if v >= n:
        right = mid
    else:
        left = mid
print(right)

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001


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


def is_OK(P):
    track_index = 0
    w_index = 0
    while w_index < N and track_index < K:
        tmp_sum = 0
        while  w_index < N and tmp_sum+W[w_index] <= P:
            tmp_sum += W[w_index]
            w_index += 1
        track_index += 1
    return w_index == N

L = 0
R = 100000*100000
mid = (L+R)//2
ans = R

while L <= R:
    if is_OK(mid):
        ans = mid
        R = mid-1
    else:
        L = mid+1
    mid = (L+R)//2

print("%d"%ans)

Submission status: Accepted

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

def f(P):
    v = 0
    for j in range(k):
        a = 0
        while(a+s[v]<=P):
            a += s[v]
            v+=1
            if v==n:
                return v
    return v

l = 0
r = 10**9
while l!=r:
    mid = (l+r)//2
    c = f(mid)
    if c>=n:
        r = mid
    else:
        l = mid+1   
print(r)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
w = [int(input()) for _ in range(n)]
s = max(w)-1
w.append(10**13)
t = sum(w)

while s+1 < t:
	m = (s + t) // 2
	x = 0
	c = 0
	for i in range(n+1):
		c += w[i]
		if c > m:
			x += 1
			c = w[i]
		elif c == m:
			if i != n-1:
				x += 1
				c = 0
	if x > k:
		s = m
	else:
		t = m

print(t)

Submission status: Accepted

Solution code:
def judge_1(arr, p, k):
    index = 0
    n = len(arr)
    for i in range(k):
        weight_sum = 0
        while weight_sum + arr[index] <= p:
            weight_sum += arr[index]
            index += 1
            if index >= n:
                return True
    return index >= n


if __name__ == '__main__':
    n, k = map(int, input().split())
    weight = []
    l, r = 0, 0
    for _ in range(n):
        tmp = int(input())
        weight.append(tmp)
        r += tmp
        l = max(l, tmp)
    ans = r
    while l <= r:
        mid = (l + r) // 2
        if judge_1(weight, mid, k):
            ans = mid
            r = mid - 1
        else:
            l = mid + 1
    print(ans)

Submission status: Accepted

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

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

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

print(Binaryserch())

Submission status: Accepted

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

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


def solve():
	r = 1000000000
	l = 0
	while r-l > 1:
		mid = int((r+l)/2)
		v = check(mid)
		if(v >= n):
			r = mid
		else:
			l = mid
	return r

print(solve())

Submission status: Accepted

Solution code:
#17D8104026C 宮地拓海 Air_conditioner123 Python

def check(mid):
	global k, T, n

	i = 0
	for j in range(k):
		s = 0
		while s + T[i] <= mid:
			s += T[i]
			i += 1
			if (i == n):
				return n	
	return i

n, k = map(int, input().split())
T = [int(input()) for i in range(n)]
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:
n,k=map(int,input().split())
w=[int(input()) for i in range(n)]
left=max(w)-1;right=sum(w)
mid=0
while left+1<right:
    mid=(left+right)//2
    sum=0;count=1
    for wi in w:
        if wi+sum>mid:
            sum=wi
            count+=1
        else:
            sum+=wi
    if count<=k:
        right=mid
    else:
        left=mid

print(right)