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: Wrong Answer

Solution code:
num, track = [int(x) for x in input().split()]
hoge = 0
for _ in range(num):
    hoge += int(input())
if hoge % track == 0:
    print (hoge // track)
else:
    print (hoge // track + 1)

Submission status: Wrong Answer

Solution code:
num, track = [int(x) for x in input().split()]
hoge_l = list()
for _ in range(num):
    hoge_l.append(int(input()))
hoge_i = sum(hoge_l)
if hoge_i % track == 0:
    hoge_i = hoge_i // track
else:
    hoge_i = hoge_i // track + 1

tmp = 0
c = 1
for v in hoge_l:
    tmp += v
    if tmp > hoge_i:
        c += 1
        tmp = 0
        tmp += v
if c == track:
    print (hoge_i)
elif c > track:
    print (hoge_i+1)

Submission status: Wrong Answer

Solution code:
num, track = [int(x) for x in input().split()]
hoge_l = list()
for _ in range(num):
    hoge_l.append(int(input()))
hoge_i = sum(hoge_l)
if hoge_i % track == 0:
    hoge_i = hoge_i // track
else:
    hoge_i = hoge_i // track + 1

while True:
    tmp = 0
    c = 1
    for v in hoge_l:
        tmp += v
        if tmp > hoge_i:
            c += 1
            tmp = 0
            tmp += v
    if c == track:
        break
    elif c > track:
        hoge_i += 1
print (hoge_i)

Submission status: Wrong Answer

Solution code:
num, track = [int(x) for x in input().split()]
hoge_l = list()
for _ in range(num):
    hoge_l.append(int(input()))
hoge_i = sum(hoge_l)
if hoge_i % track == 0:
    hoge_i = hoge_i // track
else:
    hoge_i = hoge_i // track + 1

while True:
    tmp = 0
    c = 1
    for v in hoge_l:
        tmp += v
        if tmp > hoge_i:
            c += 1
            tmp = 0
            tmp += v
    print (c)
    if c == track:
        break
    elif c > track:
        hoge_i += 1
max_num = max(hoge_l)
if max_num > hoge_i:
    hoge_i = max_num
print (hoge_i)

Submission status: Wrong Answer

Solution code:
def imas(hoge_l, p, track):
    s = 0
    now_track = 1
    for v in hoge_l:
        s += v
        if s > p:
            s = 0
            now_track += 1
            s += v
        if now_track > track:
            return 'PisSmall'
    if now_track <= track:
        return 'PisBig'

num, track = [int(x) for x in input().split()]
hoge_l = list()
for _ in range(num):
    hoge_l.append(int(input()))
left = 0
right = 100000 * 10000

while left < right:
    mid = (right + left) // 2
    if imas(hoge_l, mid, track) == 'PisSmall':
        left = mid + 1
    elif imas(hoge_l, mid, track) == 'PisBig':
        right = mid
max_num = max(hoge_l)
if max_num > mid:
    mid = max_num
print (mid)

Submission status: Wrong Answer

Solution code:
def imas(hoge_l, p, track):
    s_weights = 0
    now_track = 1
    for val in hoge_l:
        s_weights += val
        if s_weights > p:
            s_weights = val
            now_track += 1
        if now_track > track:
            return False
    return True

num, track = [int(x) for x in input().split()]
hoge_l = list()
for _ in range(num):
    hoge_l.append(int(input()))
left = 0
right = 100000 * 10000

while left < right :
    mid = (right + left) // 2
    if imas(hoge_l, mid, track):
        right = mid 
    else:
        left = mid + 1
        
max_num = max(hoge_l)
if max_num > mid:
    mid = max_num
print (right)

Submission status: Wrong Answer

Solution code:
import sys
n,k=map(int,input().split())
w=list(map(int,sys.stdin.readlines()))
def check():
 c=t=0
 for j in w:
  t+=j
  if t>m:
   t=j
   c+=1
   if c>=k:return 0
 return 1
l,r=max(w),sum(w)
while r-l>1:
 m=(l+r)//2
 if check():r=m
 else:l=m
print(r)

Submission status: Wrong Answer

Solution code:
import sys
n,k=map(int,input().split())
w=list(map(int,sys.stdin.readlines()))
def f():
 c,t=1,0
 for j in w:
  t+=j
  if t>m:
   t=j
   c+=1
   if c>k:return 0
 return 1
l,r=max(w),sum(w)
while r-l>1:
 m=(l+r)//2
 if f():r=m
 else:l=m
print(l)

Submission status: Wrong Answer

Solution code:
import sys
n,k=map(int,input().split())
w=list(map(int,sys.stdin.readlines()))
def f():
 c=t=0
 for j in w:
  t+=j
  if t>m:
   t=j
   c+=1
   if c>k:return 0
 return 1
l,r=max(w),sum(w)
while r-l>=1:
 m=(l+r)//2
 if f():r=m
 else:l=m
print(r)

Submission status: Wrong Answer

Solution code:
import sys
n,k=map(int,input().split())
w=list(map(int,sys.stdin.readlines()))
def f():
 c=t=0
 for j in w:
  t+=j
  if t>m:
   t=j
   c+=1
   if c>=k:return 0
 return 1
l,r=max(w),sum(w)
while l<r:
 m=(l+r)//2
 print(l,m,r)
 if f():r=m
 else:l=m+1
print(r)

Submission status: Wrong Answer

Solution code:
import sys
n,k=map(int,input().split())
w=list(map(int,sys.stdin.readlines()))
def f():
 i=0
 for _ in[0]*k:
  s=0
  while s+w[i]<=m:
   s+=w[i];i+=1
   if i==n:return n
 return i
l,r=max(w),sum(w)
while l<r:
 m=(l+r)//2
 if f()>=n:r=m
 else:l=m+1
print(l,m,r)

Submission status: Wrong Answer

Solution code:
import sys
def s():
 n,k=map(int,input().split())
 w=list(map(int,sys.stdin.readlines()))
 def f():
  c=t=0
  for j in w:
   t+=j
   if t>m:
    t=j
    c+=1
    if c>=k:return 0
  return 1
 l,r=max(w),sum(w)
 while l<r:
  m=(l+r)//2
  print(l,m,r)
  if f():r=m
  else:l=m+1
 print(r)
if'__main__'==__name__:s()

Submission status: Wrong Answer

Solution code:
def cnt_car(w, p):
    car = 0
    wi = 0
    for i in w:
        if (wi + i) <= p:
            wi += i
        else:
            car += 1
            wi = i
    return car

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

Submission status: Wrong Answer

Solution code:
import sys
import heapq


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

    >>> allocate(3, [1, 3, 7, 8, 9])
    10
    >>> allocate(2, [1, 2, 2, 6])
    6
    """

    if len(weights) <= count:
        return weights[-1]

    trucks, rest = weights[-count:], weights[:-count]
    heapq.heapify(trucks)

    while len(rest) > 0:
        minl = heapq.heappop(trucks)
        heapq.heappush(trucks, minl + rest.pop())

    return [heapq.heappop(trucks) for _ in range(count)][-1]


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

    print(allocate(n, sorted(ws)))


if __name__ == '__main__':
    run()

Submission status: Wrong Answer

Solution code:
import sys

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

    >>> allocate(2, [1, 2, 2, 6])
    6
    >>> allocate(3, [8, 1, 7, 3, 9])
    10
    """
    def sumw(i, j): 
        if (i, j) not in sums:
            sums[(i, j)] = sum(weights[i:j])
        elif (i, j-1) in sums:
            sums[(i, j)] = sums[(i, j-1)] + weights[j-1]

        return sums[(i, j)] 

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

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

    return min(maxloads)

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

    print(allocate(n, ws))


if __name__ == '__main__':
    run()

Submission status: Wrong Answer

Solution code:
import sys


def allocate(count, weights):
    def loadable_counts(maxweight):
        n = 0 
        l = 0 
        c = count
        for w in weights:
            l += w
            if l > maxweight:
                l = w 
                c -= 1

            if c <= 0:
                return n

            n += 1
        return n

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

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

    return i



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

    print(allocate(n, ws))


if __name__ == '__main__':
    run()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Apr 30 15:18:29 2018
ALDS1-4c
@author: maezawa
"""

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

for i in range(n):
    w.append(int(input()))
w.sort(reverse=True)

i = 0
while i<n:
    tr.sort()
    tr[0] += w[i]
    i += 1

p = max(tr)

print(p)

Submission status: Wrong Answer

Solution code:

Submission status: Wrong Answer

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


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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:

n,t=[int(x) for x in input().split()]
w=[]
for i in range(n):
    w.append(int(input()))

totalw=sum(w)  
pmax=totalw
pmin=int(totalw/t)

def check(ptest):
    tk=1
    p=0
    global t
    global w
    global n
    i=0
    
    while i<n:
        p+=w[i]
        if p<=ptest:
            i+=1
        else:
            tk+=1
            p=0
            
        if tk>t:
            return 0
            break   
    
    return 1
    
        
while (pmax-pmin)>1:
    pmid=pmin+(pmax-pmin)//2
    if check(pmid)==1:
        pmax=pmid
    else:
        pmin=pmid
        
print(pmax)

Submission status: Wrong Answer

Solution code:


n,k=map(int,input().split())
W=[int(input()) for i in range(n)]
 
left = int(sum(W)/k); right = sum(W)
while left+1 < right:
    mid = (left + right)//2
    cnt = 1
    now = 0
    for i in W:
        if mid<now+i:
            now=i
            cnt+=1
        else:
            now+=i
    if cnt<=k:
        right=mid
    else:
        left=mid

print(right)

Submission status: Wrong Answer

Solution code:
#coding: Shift_JIS

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

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

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

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


print(p)

Submission status: Wrong Answer

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

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


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

    while True:

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

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


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

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

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

print(ps[mid])

Submission status: Wrong Answer

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

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


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

    while True:

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

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


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

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

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

print(ps[left])

Submission status: Wrong Answer

Solution code:
def ok(m):
    c = 1
    tmp = m
    for w in W:
        if tmp > w:
            tmp -= w
        else:
            c += 1
            tmp = m - w
    return k >= c

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

left = max(W)
right = sum(W)
while left+1 < right:
    mid = (left+right) // 2
    if ok(mid):
        right = mid
    else:
        left = mid
print(left)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
all_w = 0
for i in range(n):
    all_w += int(input())
if all_w % k:
    print(all_w // k + 1)
else:
    print(all_w // k)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
all_w = []
for i in range(n):
    all_w.append(int(input()))
average = sum(all_w) // k
total = 0; a = []
for i in all_w:
    if total < average:
        total += i
    else:
        a.append(total)
        total = 0
        total += i
a.append(total)
print(max(a))

Submission status: Wrong Answer

Solution code:
def insert(t, w):
    length = len(t)
    x = t[length - 1] + w
    t.pop()
    l = 0
    r = length - 1
    while l < r:
        ind = (l + r) // 2
        if t[ind] == x:
            t.insert(ind, x)
            return t
        elif t[ind] < x:
            r = ind
        else:
            l = ind + 1
    t.insert(l, x)
    return t


nk = input().split()
n = int(nk[0])
k = int(nk[1])
ws = []
for _ in range(n):
    ws.append(int(input()))
ws.sort()
ws.reverse()
trac = [0] * k
for w in ws:
    trac = insert(trac, w)
    #print(trac)

print(max(trac))

Submission status: Wrong Answer

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

def main():
    n, k = map(int, stdinput().split())
    w = list(map(int, [stdinput() for _ in range(n)]))
    avg = sum(w) // k + 1

    # monban
    w.append(10**5)

    max_w = -1
    this_w = 0
    for i in range(n+1):
        next_w = w[i]
        if this_w + next_w > avg:
            if this_w > max_w:
                max_w = this_w
            this_w = 0
        this_w += next_w
    
    print(max_w)

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

Submission status: Wrong Answer

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

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

L = max(w)
R = sum(w) // k + 1

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

print(R)

Submission status: Wrong Answer

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

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

L = max(w)
R = sum(w) // k + 1

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

print(R)

Submission status: Wrong Answer

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

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

L = max(w)
R = sum(w)

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

print(R)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
def can_load(baggages, trucks, max_load):
    truck_list = [max_load for x in range(trucks)]

    for truck in truck_list:
        while truck > 0:
            if len(baggages) == 0:
                #print(max_load,"True")
                return True
            if truck >= baggages[0]:
                truck -= baggages[0]
                baggages.pop(0)
            else:
                break
    #print(max_load, len(baggages) == 0)
    return len(baggages) == 0

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

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

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

    print(start)
    return


main()

Submission status: Time Limit Exceeded

Solution code:
def check(P):
    lis = [[] for i in range(k)]
    su = [0 for i in range(k)]
    
    su.append(-10000)
    for i, bag in enumerate(baggage):
        cur = 0
        #print(su,cur,su[cur])
        while su[cur] + bag > P:
            cur += 1
        if cur == k:
            return False
        else:
            lis[cur].append(bag)
            su[cur] += bag
    #print(lis, su, P)
    return True

def main():
    min_P = 1000000000
    left = 1
    right = 1000000000
    while left < right:
        mid = (left + right)//2 + 1
        #print(left, mid, right, end=" ")
        if check(mid):
            right = mid
            if min_P > mid:
                min_P = mid
        else:
            left = mid+1
    
    #print(left,right)
    print(min_P)
       
if __name__ == '__main__':
    n, k = map(int, input().rstrip().split(" "))
    #n,k= 5,3
    baggage = [int(input()) for i in range(n)]
    #baggage = [8,1,7,3,9]
    
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, k = map(lambda x: int(x), input().split())
    w = [int(input()) for _ in range(n)]
    cumulative_sum = [0]
    for i in w:
        cumulative_sum.append(cumulative_sum[-1] + i)
    p = max(max(w), sum(w)//k)
    while True:
        left_track = k
        capacity = 0
        for weight in w:
            if capacity + weight <= p:
                capacity += weight
            else:
                left_track -= 1
                capacity = weight
                if left_track == 0:
                    p += 1
                    break
        else:
            break
    print(p)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

# print(loads)
slices = []
min_load = [99999999999999]


def slicing(rest, s):
    if not rest:
        # slices.append(s+[(len(s) and s[-1][1], len(loads))])
        s += [(len(s) and s[-1][1], len(loads))]
        min_load[0] = min(min_load[0], max(sum(loads[l[0]: l[1]]) for l in s))
        return

    first = len(s) and s[-1][1]
    for s1 in range(first+1, len(loads)-rest+1):
        total = sum(loads[first: s1])
        if total < min_load[0]:
            slicing(rest-1, s+[(first, s1)])


slicing(tracks-1, [])
print(min_load.pop())

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache


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

# print(loads)
slices = []
min_load = [99999999999999]

@lru_cache()
def slicing(rest, s=0):
    if not rest:
        # slices.append(s+[(len(s) and s[-1][1], len(loads))])
        return sum(loads[s:])

    result = 99999999999999
    for s1 in range(s+1, len(loads)-rest+1):
        result = min(result, max(sum(loads[s: s1]), slicing(rest-1, s1)))
    return result


rs = slicing(tracks-1)
print(rs)
# print(slices)


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


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

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache


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

# print(loads)
slices = []
min_load = [99999999999999]

@lru_cache()
def slicing(rest, s=0):
    if not rest:
        # slices.append(s+[(len(s) and s[-1][1], len(loads))])
        return sum(loads[s:])

    result = 99999999999999
    for s1 in range(s+1, len(loads)-rest+1):
        sub_total = sum(loads[s: s1])
        if sub_total <= result:
            result = min(result, max(sub_total, slicing(rest-1, s1)))
    return result


rs = slicing(tracks-1)
print(rs)
# print(slices)


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


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

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache


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

# print(loads)
slices = []
min_load = [99999999999999]

@lru_cache()
def slicing(rest, s=0):
    if not rest:
        # slices.append(s+[(len(s) and s[-1][1], len(loads))])
        return sum(loads[s:])

    result = 99999999999999
    for s1 in range(s+1, len(loads)-rest+1):
        sub_total = sum(loads[s: s1])
        if sub_total > result:
            break
        result = min(result, max(sub_total, slicing(rest-1, s1)))
    return result


rs = slicing(tracks-1)
print(rs)
# print(slices)


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


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

Submission status: Time Limit Exceeded

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

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

p = max(l)
while True:
    sm_k = 0
    k_no = 1
    for li in l:
        if sm_k + li > p:
            k_no += 1
            sm_k = li
        else:
            sm_k += li

    # print(p, k_no)
    if k_no <= k:
        print(p)
        break

    p += 1

Submission status: Time Limit Exceeded

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

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

p = max(l)
while True:
    sm_k = 0
    k_no = 1
    for li in l:
        if sm_k + li > p:
            k_no += 1
            if k_no > k:
                break
            sm_k = li
        else:
            sm_k += li

    # print(p, k_no)
    if k_no <= k:
        print(p)
        break

    p += 1

Submission status: Time Limit Exceeded

Solution code:
import math

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

wsum = sum(w)

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

P = max(int(math.ceil(wsum / k)), max(w))

while not loadable(w, n, k, P, wsum):
    P += 1
print(P)

Submission status: Time Limit Exceeded

Solution code:
import math, sys

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

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

wsum = sum(w)

P = max(int(math.ceil(wsum / k)), max(w))

while not loadable(w, n, k, P, wsum):
    P += 1
print(P)

Submission status: Time Limit Exceeded

Solution code:
import math, sys

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

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

wsum = sum(w)

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

while True:
    if loadable(w, n, k, p, wsum):
        if p - pre_f == 1:
            break
        pre_s = p
        p = int((p + pre_f) /2)
    else:
        pre_f = p
        if pre_s:
            p = int((pre_s + p) / 2)
        else:
            p = math.ceil(p * 1.01)
    
print(p)

Submission status: Time Limit Exceeded

Solution code:
n, k = [ int( val ) for val in raw_input( ).split( " " ) ]
w = [ int( raw_input( ) ) for val in xrange( n ) ]
sumW = sum( w )
maxW = max( w )

minP = 0
if 1 == k:
	minP = sumW
elif n == k:
	minP = maxW
else:
	minP = max( maxW, sumW//k )
	while True:
		truckCnt = i = loadings = 0
		while i < n:
			loadings += w[i]
			if minP < loadings:
				truckCnt += 1
				if k < truckCnt+1:
					break
				loadings = w[i]
			i += 1
		if truckCnt+1 <= k:
			break

		minP += 1

print( minP )

Submission status: Time Limit Exceeded

Solution code:
def need(A, p):
    if max(A) > p:
        return 100001
    count = 0
    track = 0
    for x in A:
        if count + x <= p:
            count += x
        else:
            track += 1
            count = x
    if count > 0:
        return track + 1
    else:
        return track

n, k = map(int, raw_input().split())
W = [int(raw_input()) for i in xrange(n)]

left = 1
right = sum(W) + 1
while left < right:
    mid = (left + right) / 2
    track = need(W, mid)
    if k == track:
        while k == need(W, mid-1):
            mid -= 1
        print mid
        quit()
    elif k > track:
        right = mid
    else:
        left = mid + 1
if left == right:
    print left

Submission status: Time Limit Exceeded

Solution code:
def maxStack(k, p, W):
    nw = 0
    count = 0
    t = 1
    for x in W:
        if x > p:
            return count
        if nw + x <= p:
            nw += x
            count += 1
        else:
            if t == k:
                return count
            else:
                t += 1
                nw = x
                count += 1
    return count


n, k = map(int, raw_input().split())
W = [int(raw_input()) for i in xrange(n)]

left = 1
right = sum(W)
while left < right:
    mid = (left + right) / 2
    v = maxStack(k, mid, W)
    if v == n:
        while n == maxStack(k, mid-1, W):
            mid -= 1
        print mid
        quit()
    elif v > n:
        right = mid
    else:
        left = mid + 1
print left

Submission status: Time Limit Exceeded

Solution code:
"""Allocation argorithm."""

def carriable_baggage(baggage, baggage_num, truck_capacity, truck_num):
    """Return the number of baggae which trucks can carry."""
    carried_baggage = 0
    for i in range(truck_num):
        laden_weight = 0
        while laden_weight < truck_capacity and carried_baggage < baggage_num:
            laden_weight += baggage[carried_baggage]
            carried_baggage += 1
        if laden_weight > truck_capacity:
            carried_baggage -= 1
        if carried_baggage == baggage_num:
            return carried_baggage
    return carried_baggage

def min_capacity(baggage, baggage_num, truck_num):
    """Return the minimum value of maximum load capacity of trucks."""
    heaviest_baggage = max(baggage)
    average_capacity = sum(baggage) // truck_num
    capacity = max(heaviest_baggage, average_capacity)
    while carriable_baggage(baggage, baggage_num, capacity, truck_num) < baggage_num:
        capacity += 1
    return capacity


import sys

baggage_num, truck_num = map(int, sys.stdin.readline().split())

baggage = list(map(int, sys.stdin))

capacity = min_capacity(baggage, baggage_num, truck_num)

print(capacity)