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:
from sys import stdin
import sys
import math
n,k=list(map(int,(stdin.readline().strip().split())))
w=[int(input()) for x in range(n)]
def f(p):
    i=0
    for j in range(k):
        weight=0
        while(weight+w[i]<=p):
            weight+=w[i]
            i+=1
            if i==n:return n
    return i
left=0
right=10**9+1
mid=right//2
while(True):
    length=f(mid)
    if length==n:
        l=f(mid-1)
        if length==l:
            right=mid
            mid=(right+left)//2
        else:
            print(mid)
            exit()
    if length>n:
        right=mid
        mid=(right+left)//2
    if length<n:
        left=mid
        mid=(right+left)//2

Submission status: Accepted

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


def check(p):
    remain_track = k - 1
    remain_p = p
    for a in range(n):
        if w[a] > p:
            return False
        if remain_p >= w[a]:
            remain_p -= w[a]
        else:
            if remain_track == 0:
                return False
            else:
                remain_track -= 1
                remain_p = p - w[a]
        # print(a, w[a], remain_p, remain_track)
    return True


next = 10 ** 9
prev = next


for i in range(200):
    if check(next):
        prev = next
        next = next // 2
    else:
        next = (next + prev) // 2
print(prev)

Submission status: Accepted

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

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 True
    return False

ng, ok = 0, 10**9
while ok-ng > 1:
    mid = (ng+ok)//2
    if check(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Accepted

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

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

minP = max(max(w), sum(w)//k)
maxP = sum(w)
    
left = minP
right = maxP

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

        if cnt_track > k:
                flag = 0
                break
    if flag:
        right = mid
    else:
        left = mid + 1
            
print(left)

Submission status: Accepted

Solution code:
import math

_=list(map(int,input().split()))
n,k=_[0],_[1]
W=[]
for i in range(n):
    W.append(int(input()))

def n_cal(num_track,weights,threshold):
    numbers_=0
    for i in range(num_track): #each tracktor
        sum_=0
        while sum_<=threshold and numbers_<=len(weights)-1: #each tracktor's capacity
            sum_+=weights[numbers_] #each tracktor's weight
            if sum_<=threshold:numbers_+=1
            else:pass
    return numbers_

minimum_=max(W)
maximum_=sum(W)
P=range(minimum_,maximum_+1)

left=0;right=len(P)
mid=math.floor((left+right)/2)
while left<right:
    if n_cal(k,W,P[mid])<n:
        left=mid+1
    elif n==n_cal(k,W,P[mid]) and n==n_cal(k,W,P[mid-1]):
        right=mid
    else:break
    mid=math.floor((left+right)/2)
print(P[mid])

Submission status: Accepted

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

def track_search(mid):
    count_track = 1
    cnt = 0
    for i in w:
        if i+cnt<=mid:
            cnt+=i
        else:
            count_track += 1
            cnt = i
    return count_track


def weight_search():
    global ans
    right = sum(w)+1
    left = max(w)
    while right>left:
        mid = (right+left)//2
        track = track_search(mid)
        if track>k:
            left = mid+1
        else:
            right = mid
            ans = mid
    return ans

print(weight_search())

Submission status: Accepted

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

# 最大積載量p でk台のトラックに全ての荷物を積載できるかチェックする
def check(p):
  global n, k, w

  # k台のトラックに積載済の荷物の個数
  i = 0

  # k台のトラックに順番に荷物を積載する
  for j in range(k):
    # j台目のトラックの積載量の合計
    s = 0

    # 積載量の合計が 最大積載量p を超えるまで荷物を積み込む
    while (s + w[i] <= p):
      s += w[i]
      
      # トラックに積載済の荷物の個数をカウントアップ
      i += 1

      # 最大積載量p で すべての荷物を積み込めた場合
      if (i == n):
        return True

  # 最大積載量p で すべての荷物を積み込めなかった場合
  return False


# メイン処理
def solve():
  global n

  # 積載量の下限
  left = 0

  # 積載量の上限（個数の最大値 × 重量の最大値）
  right = 100000 * 10000

  while (1 < right - left):
    # 最大積載量p
    p = int((left + right) / 2)

    if check(p):
      # 最大積載量pで全ての荷物が積み込めた場合、p より小さい範囲を探索
      right = p
    else:
      # 最大積載量pで全ての荷物が積み込めなかった場合、p より大きい範囲を探索
      left = p
  
  # 全ての荷物を積み込むことができた最小の最大積載量を返却する
  return right

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

Submission status: Accepted

Solution code:
# 最大積載量p でk台のトラックに全ての荷物を積載できるかチェックする
def check(p):
  global n, k, w

  # k台のトラックに積載済の荷物の個数
  i = 0

  # k台のトラックに順番に荷物を積載する
  for j in range(k):
    # j台目のトラックの積載量の合計
    s = 0

    # 積載量の合計が 最大積載量p を超えるまで荷物を積み込む
    while (s + w[i] <= p):
      s += w[i]
      
      # トラックに積載済の荷物の個数（合計）をカウントアップ
      i += 1

      # 最大積載量p で すべての荷物を積み込めた場合
      if (i == n):
        return True

  # 最大積載量p で すべての荷物を積み込めなかった場合
  return False


# メイン処理
def solve():
  global n

  # 積載量の下限
  left = 0

  # 積載量の上限（個数の最大値 × 重量の最大値）
  right = 100000 * 10000

  while (1 < right - left):
    # 最大積載量p
    p = int((left + right) / 2)

    if check(p):
      # 最大積載量pで全ての荷物が積み込めた場合、p より小さい範囲を探索
      right = p
    else:
      # 最大積載量pで全ての荷物が積み込めなかった場合、p より大きい範囲を探索
      left = p
  
  # 全ての荷物を積み込むことができた最小の最大積載量を返却する
  return right

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

Submission status: Accepted

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

def check(x):
    cnt, tmp = 0, 0
    for i in range(n):
        if x < arr[i]:
            return False
        elif tmp + arr[i] > x:
            tmp = arr[i]
            cnt += 1
        else:
            tmp += arr[i]
        if i == n - 1 and tmp > 0:
            cnt += 1
    return cnt <= k

l, r = 1, int(1e9 + 1)
while l < r:
    mid = (l + r) >> 1
    if check(mid):
        r = mid
    else:
        l = mid + 1
print(l)

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:
#???
n,k = map(int,input().split())
l=[int(input()) for _ in range(n)]

def check(p):
    j=0
    for _ in range(k):
        sum=0
        """
        if l[j]>p: #そもそもある一個の荷物の重さがpを超える場合
            return False #j=0の瞬間から引っかかったとしてもwhileには入らないので、k回ループの後どうせfalseになる
            """
        while sum+l[j] <= p:
            sum+=l[j]
            j+=1
            if j==n:
                return True
    return False

#binarysearch
L=0
R=10000*100000
ans=0
while L<=R:
    M = (L+R) // 2
    if check(M):
        ans=M
        R=M-1#最終的にこの行のRを答えとして出そうとすると、実際の最小値より下回ってしまうことがあるので注意。
            #この行は次のbinarysearchに進む前提で更新しているのでこれを出力しない
    else:
        L=M+1
print(ans)


# もし，仮に，Pが決まっていたら前から貪欲にギリギリまで物を詰めるのが最適
# そうすることで必要なトラックの数を最小に抑えることができる
#
"""
#include <iostream>

using namespace std;

#define rep(i, n) REP(i,0,n)
#define REP(i,a,n) for(int i = a ; i < (int)n ; i++)

typedef long long ll;

int n, k;
int w[100001];
#二分探索を進めてPの最小値を決定する
bool check(int p){ #Pの値を二分探索して，判定関数はそのPの値でk台以内で荷物を積み切れるか
  #を判定、積み切れるならtrue->さらに小さい値からPを探す(right(最大値)を小さくする)。
  # 積み切れないならfalse->さらに大きい値からPを探す(left(最小値))を大きくする。
  ll sum=0;
  int idx = 0;

  rep(i, k){#k台以内に全ての荷物を積み切れるか？
    sum = 0;
    while(w[idx] + sum <= p){#k以内ならwhileは何回入ってもいい、入り直すたびにトラックが新しくなる(sum=0にする)
      sum+=w[idx];
      idx++;
      if(idx == n) return true;
    }
  }
  return false;
}

signed main(){
  cin >> n >> k;

  rep(i, n) cin >> w[i];
  
  // binary search
  ll left = 0, right = 100000 * 10000;#もしトラックの数が１台しかなければ全ての荷物が最大重量の場合(w_i=10000)をその最大個数分(n=100000)積めなくてはならないのでこれがPの最悪計算量(最大値)
  while(right - left > 1){
    ll mid = (left + right) / 2;
    if(check(mid)) right = mid;
    else left = mid;
  }
  
  cout << right << endl;
}
"""

Submission status: Accepted

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

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

left = 0
right = 100000 * 10000
mid = 0
while 1 < right - left:
    mid = (left + right) / 2
    v = check(mid)
    if v >= N:
        right = mid
    else:
        left = mid

print(int(right))

Submission status: Accepted

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

def check(m):
    need = 1
    sm = 0
    for w in ws:
        if w > m:
            return False
        if sm + w > m:
            need += 1
            sm = w
        else:
            sm += w
    return need <= k

lw = 0
hi = 10**10
ans = hi
while lw <= hi:
    mid = (lw + hi) // 2
    if check(mid):
        ans = mid
        hi = mid - 1
    else:
        lw = mid + 1

print(ans)

Submission status: Accepted

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

# k台以内のトラックで運べる荷物の個数
# P: ひとつのトラックに積載できる最大量
def check(P):
	i = 0
	for j in range(k):
		s = 0
		while s + w[i] <= P:
			s += w[i]
			i += 1
			if i == n:
				return n
	return i

# 二部探索
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 = []
for _ in range(n):
    W.append(int(input()))


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


def binary_search(left, right):
    while left < right:
        m = (left + right) // 2
        c = is_carry(m)
        if c:
            right = m
        else:
            left = m + 1
    print(left)


left = 0
right = 100_000 * 100_000
binary_search(left, right)

Submission status: Accepted

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

def delivable(m):
    loading=0
    track_num=1
    for i in range(n):
        if w[i] > m:
            return False
            break
        else:
            loading += w[i] 
            if loading > m:
                loading=w[i]
                track_num += 1
    if track_num <= k:
        return True
    else:
        return False


r=1000000000
l=min(w)-1
while r-l > 1:
    m=(r+l)//2
    if delivable(m):
        r=m
    else:
        l=m

print(r)

Submission status: Accepted

Solution code:
def f(n, k, W):
    sum = 0
    i = 0
    while k > 0 and i < len(W):
        sum += W[i]
        if sum <= n:
            i += 1
        else:
            sum = 0
            k -= 1
    if k == 0:
        return False
    else:
        return True


n ,k = [int(_) for _ in input().split()]
W = []
for i in range(n):
    W.append(int(input()))
low = 0
high = 10 ** 9
while low + 1 < high:
    mid = (low + high) // 2
    # print("mid", mid)
    # print("low", low)
    # print("high", high)
    # print("f", f(mid, k, W))
    # print("-----------------------")
    if f(mid, k, W):
        high = mid
    else:
        low = mid
print(high)

Submission status: Accepted

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

    def check(P):
        s = 0
        res = 1
        for b in a:
            if P<b:return False
            if P<s+b:
                s = b
                res+=1
            else :s+=b
        return k>=res

    l,r = 0,1000000007
    m = 0
    while l<r-1:
        m = (l+r)//2
        if check(m):r = m
        else       :l = m
    print(r)



if __name__ == '__main__':
    main()

Submission status: Accepted

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

right = sum(W)
left = max(W)-1

while left + 1< right:
    cnt = 1
    cur = 0
    mid = (right + left) // 2
    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:
n, k = list(map(int,input().split()))
w = list()
for _ in range(n):
  w.append(int(input()))

w_sum = sum(w)



def f(p):
  v = 0
  for _ in range(k):
    s = 0
    while s + w[v] <= p:
#      print("add", w[v])
      s += w[v]
      v += 1
      if v == n:
        return v
  return v


def search(a, l, r, f):
  while r - l > 1 :
    m = (l + r) // 2
    v = f(m)
    if  v >= n:
      r = m 
    else:
      l = m
  return r

res = search(n, 0, 10000 * 100000, f)
print(res)

Submission status: Accepted

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

#最大積載量pとした時のチェック
def check(p):
    sumw=0
    idx=0

    for i in range(k):
        sumw=0
        while(w[idx]+sumw<=p):
            sumw+=w[idx]
            idx+=1
            if(idx==n):
#                print("{0}台で運べる:w[{1}]まで、 積載量{2} 最大積載量{3} ".format(i+1,idx,sumw,p))
                return True
#            print("runT:{0} {1} {2} k={3}".format(idx,sumw,p,i))
#        print("{0}台目:w[{1}]まで、 積載量{2} 最大積載量{3}".format(i+1,idx-1,sumw,p))
#    print("運べない:w[{0}]でアウト 積載量{1} 最大積載量{2} k={3}".format(idx,sumw,p,k-1))
    return False

left=0
right=100000*10000

while(right - left > 1):
    mid = (left + right)//2
#    print("最大積載量p:{0}".format(mid))
    if(check(mid)):
        right=mid
    else:
        left=mid
#    print("main:left:{0} right:{1} mid:{2}".format(left,right,mid))

print(right)

Submission status: Accepted

Solution code:
def n_nimotsu_if_P(P, k, arr):
	weight = 0
	n_trucks = 1
	for i, a in enumerate(arr):
		if P < a:
			return i
		if weight + a <= P:
			weight += a
		else:
			n_trucks += 1
			weight = a
		if n_trucks == k + 1:
			return i

	return len(arr)

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

left, right = 0, 10000 * n
i_break = 0
while right - left > 1:
	mid = (left + right) // 2
	if n <= n_nimotsu_if_P(mid, k, luggages):
		right = mid
	else:
		left = mid

print(right)

Submission status: Accepted

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

left = 0
right = 100000*10000

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

Submission status: Accepted

Solution code:
import math

def search(cap, loads, num_tracks):
    num = 0
    capacity = cap
    tracks = num_tracks

    for l in loads :
        if capacity >= l: 
            capacity -= l
            num += 1
        else:
            if tracks > 1:
                tracks -= 1
                capacity = cap

                if capacity >= l:
                    capacity -= l
                    num += 1
                else:
                    break
            else:
                break
    return num

def Main():
    N, K = map(int, input().split())
    loads = list()

    for i in range(N):
        l = int(input())
        loads.append(l)

    pl = 0
    pr = sum(loads)

    pm = int( (pl + pr)/2.0 ) + 1
    pm_ = 0

    while pl < pr :
        pm = math.ceil( (pl + pr)/2.0 )

        nl = search( pl, loads, K)
        nm = search( pm, loads, K)
        nr = search( pr, loads, K)

        if pm_ == pm:
            print(pm)
            break

        if nm == nr :
            pl = pl
            pr = pm
            pm_ = pm
        else :
            pl = pm
            pr = pr
            pm_ = pm

Main()

Submission status: Accepted

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

left = 0
right = 100000 * 10000

def check(loaded_w):
  truck_num = 1
  tmp_w = 0
  i = 0
  while i < n:
    if tmp_w + w[i] > loaded_w:
      truck_num += 1
      tmp_w = 0
    else:
      tmp_w += w[i]
      i += 1
    if truck_num > k:
      return False
  return True

while left != right:
  mid = (left + right) // 2
  if check(mid):
    right = mid
  else:
    left = mid + 1
print(left)

Submission status: Accepted

Solution code:
# Allocation
from collections import deque

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


def can_load(P):
    num_track = 1
    load = 0
    for w in W:
        if w > P:
            return False

        if load + w > P:
            if num_track == k:
                return False

            num_track += 1
            load = w

        else:
            load += w

    return True


def binary_search():
    top = 0
    bottom = sum(W)+1

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

        if can_load(P=mid):
            bottom = mid
        else:
            top = mid + 1

    return top


print(binary_search())

Submission status: Accepted

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

def check(p):
    global n,k,w
    j = 0
    for i in range(k):
        sum = 0                  # 新たなトラックになるたび,トラックに積まれている積載量を0に更新するよ
        while (sum + w[j]) <= p: # もし次の荷物を載せたら最大積載量を超えないか？？(まだsumは更新しないよ！)
            sum += w[j]          # 超えなかったからsumに加算するよ
            j += 1               # 載せられたから,jをインクリメントするよ
            if j == n:
                return n
    return j
left = 0
right = 10**9 - 1
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 = []
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:
    mid = (L+R)//2
    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:
#!/usr/bin/env python3
import sys,collections
n,k = map(int,sys.stdin.readline().split())
w = list(map(int,sys.stdin.readlines()))
ng = sum(w)//k-1
ok = sum(w)
def isOK(p):
  j = 0
  for i in range(k):
    s = 0
    while j < n and s + w[j] <= p:
      s += w[j]
      j += 1
  return j == n
while ok - ng > 1:
  mid = (ok+ng)//2
  t = collections.Counter(w)
  if isOK(mid):
    ok = mid
  else:
    ng = mid
print(ok)

Submission status: Accepted

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

def solve(n, k, W):
    left = 0
    right = (10 ** 5) * (10 ** 5)
    mid = 0
    while (right - left) > 1:
        mid = (right + left) // 2
        v = check(n, k, W, mid)
        if v >= n:
            right = mid
        else:
            left = mid
    return right

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

Submission status: Accepted

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

def check(p):
    """
    :param p: 最大積載量
    :return: 積むことができる荷物の数
    """
    global k # トラックの台数
    global t # 荷物の重さのリスト
    i = 0
    for _ in range(k):
        remaining = p
        while remaining >= t[i]:
            remaining -= t[i]
            i += 1
            if  i == len(t):
                return i
    return i

lo = 0
hi = 10**6 * 10**4

p = 0

while hi - lo > 1:
    mid = (lo + hi) // 2
    if check(mid) < n:
        lo = mid
    else:
        hi = mid
ans = hi
print(ans)

Submission status: Accepted

Solution code:
def ok(P):
    cnt = 0
    truck = 0
    for w in W + [0]:
        if w > P:
            return False
        if truck + w <= P:
            truck += w
        else:
            truck = w
            cnt += 1
    if cnt + 1 <= K:
        return True
    else:
        return False


N, K = map(int, input().split())
W = [int(input()) for _ in range(N)]
l, r = 0, 10**10
while r - l > 1:
    c = (l + r) // 2
    if ok(c):
        r = c
    else:
        l = c
print(r)

Submission status: Accepted

Solution code:

def check(P,k,staffList):
    i = 0
    for _ in range(k):
        staffNum = 0
        while(staffNum + staffList[i]<= P):
            staffNum += staffList[i]
            i += 1
            if i == n:
                return n
    return i


def getMaxP(n,k,staffList):
    # Pが増えれば，入れられる個数は単純増加するので，二部探索によりPの最小値を求められる
    left = 0
    right = 100000*10000
    while right-left>1:
        mid = (left+right)//2
        staffNum = check(mid,k,staffList)
        if staffNum >= n :
            right = mid
        else:
            left = mid

    return right


if __name__ == "__main__":
    n,k = map(int,input().split())
    staffList = [int(input()) for _ in range(n)]

    # 特定の最大積載量でどれだけ積めるのかを計算する
    P = getMaxP(n,k,staffList)

    print(P)

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

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

def Wcheck(W,P,k):
    i=0
    for j in range(k):
        temp_w=0
        while temp_w+W[i]<=P:
            temp_w=temp_w+W[i]
            i=i+1
            if i==len(W):
                return len(W)

    return i

def PSearch(W,start,end,k):
    if start==end:
        return start
    mid=(start+end)//2
    v=Wcheck(W,mid,k)
    if v>=n:
        return PSearch(W,start,mid,k)
    else:
        return PSearch(W,mid+1,end,k)

print(PSearch(W,0,1000000000,k))

Submission status: Accepted

Solution code:
def is_ok(W, limit_num, track_num):
    cu_vol = 0
    cu_tr = 0
    
    for i in range(len(W)):
        if cu_vol + W[i] > limit_num:
            cu_vol = W[i]
            cu_tr += 1
        else:
            cu_vol += W[i]
    if cu_vol:
        cu_tr += 1
    
    return track_num >= cu_tr

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

top = max(W)
tail = sum(W)
limit_num = 0

while top < tail:
    limit_num = (top + tail) // 2
    if is_ok(W, limit_num, k):
        tail = limit_num
    else:
        top = limit_num + 1

print(tail)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
#n=num of lagage
#k=num of trucks
a = []

#import sys
#input = sys.stdin.readline

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

def isOk(mx):
    num_t = 0
    t = 0
    for i in range(n):
        if a[i]>mx:
            return False
        t += a[i]
        if t>mx:
            t = a[i]
            num_t += 1
            if num_t == k:
                return False
    return True

l = sum(a)//k - 1
r = sum(a)

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

print(m)

Submission status: Accepted

Solution code:
import bisect
import math
import sys
from collections import Counter, defaultdict, deque
from copy import copy, deepcopy
from heapq import heapify, heappop, heappush
from itertools import combinations, permutations
from queue import Queue

read = sys.stdin.read
readline = sys.stdin.readline 
readlines = sys.stdin.readlines 

def SI():
    return int(readline())
def MI():
    return map(int, readline().split())
def MLI():
    return map(int, open(0).read().split())

inf = float("inf")
       
    
def check(k, P, W):
    count = 1
    tmp_sum = 0
    for w in W:
        if tmp_sum + w <= P:
            tmp_sum += w
        else:
            tmp_sum = w
            count += 1
    
    if count <= k:
        return True
    else:
        return False

def main():
    n, k, *W = MLI()
    
    lb = max(W)
    ub = sum(W)
    
    while ub - lb > 1:
        P = (lb + ub) // 2
        if check(k, P, W):
            ub = P
        else:
            lb = P
    
    if check(k, lb, W):
        print(lb)
    else:
        print(ub)
    
                
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math

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

# 最小の積載量は、最も重い荷物の重さ。または、全荷物の合計をトラック台数で割った数。
minP = max(max(W), math.ceil(sum(W) / k))
# 最大の積載量は、全荷物の合計
maxP = sum(W)

while minP < maxP:
    # 重さの最小値と最大値の半分を、積載量Pと仮定
    midP = (minP + maxP) // 2

    countTrack = 1
    calc = 0
    okFlag = True

    for w in W:
        calc += w
        
        # 積載量を超過した場合
        if calc > midP:
            # 載せずに次のトラックにまわす
            calc = w
            # トラックを1台増加
            countTrack += 1

        # トラックの最大台数を超えていたら、NG
        if countTrack > k:
            okFlag = False
            break

    # トラックの最大台数内で載せきれた場合
    if okFlag:
        # 最大値を狭めて再度処理
        maxP = midP
    else:
        # 最小値を狭めて再度処理
        minP = midP + 1

print(minP)

Submission status: Accepted

Solution code:
def check(w_list, k, P):
    tmp = 0
    tmp_k = 1
    if max(w_list) > P:
        return False
    for w in w_list:
        tmp += w
        if tmp > P:
            tmp_k += 1
            tmp = w
    if tmp_k <= k:
        return True
    else:
        return False


def binary_search(w_list, k, l, r):
    while(r - l > 1):
        c = (l + r) // 2
        # print(c)
        # print(check(w_list, k, c))
        if check(w_list, k, c):
            r = c
        else:
            l = c

    return r


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

max_P = n * 10000

min_P = binary_search(w_list, k, 0, max_P)

print(min_P)

Submission status: Accepted

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

    # 最大積載量pを算出
    min = 0
    max = 100000000000
    while min + 1 != max:
        mid =(min + max) // 2
        if check(n, k, w, mid):
            max = mid
        else:
            min = mid
    print(max)

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

if __name__ == '__main__':
    allocation()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30

def n_load(p, k, n, w):
    i = 0
    load = 0
    tr = 0
    while i < n:
        if load + w[i] <= p:
            load += w[i]
            i += 1
        else:
            tr += 1
            if tr == k:
                break
            load = 0
    return i

def main():
    n, k = list(map(int, input().strip().split()))
    w = [0] * n
    for i in range(n):
        w[i] = int(input().strip())
    l = 0
    r = INF
    while l +1 < r:
        mid = (l + r) // 2
        ntr = n_load(mid, k, n, w)
        # print('ntr: ', ntr, l, r)
        if ntr == n:
            r = mid
        else:
            l = mid
    print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline



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

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

    max_w = 10000

    max_p = max_w*n
    min_p = 0


    def number_of_track(p):
        ans = 1
        sum_w = 0
        for w in ww:
            if w > p:
                return n+1
            if sum_w + w > p:
                ans += 1
                sum_w = w
            else:
                sum_w += w
        return ans

    while min_p != max_p:
        mid = (max_p + min_p)//2
        if number_of_track(mid) <= k:
            max_p = mid
        else:
            min_p = mid+1
    print(max_p)