Problem:


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

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

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

Input

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

Output

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

Constraints

 $1 \leq n \leq 100,000$

 $1 \leq k \leq 100,000$

 $1 \leq w_i \leq 10,000$

Sample Input 1

5 3
8
1
7
3
9

Sample Output 1

10

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

Sample Input 2

4 2
1
2
2
6

Sample Output 2

6

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



Sample input:
5 3
8
1
7
3
9


Sample output:
10

Submission status: Time Limit Exceeded

Solution code:
def carriable_baggage(baggage, baggage_num, truck_capacity, truck_num):
    """Return the number of baggae which trucks can carry."""
    laden_baggage = 0
    for i in range(truck_num):
        laden_weight = 0
        while laden_weight + baggage[laden_baggage] <= truck_capacity:
            laden_weight += baggage[laden_baggage]
            laden_baggage += 1
            if laden_baggage == baggage_num:
                return baggage_num
    return laden_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)

Submission status: Time Limit Exceeded

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

def min_capacity(baggage, baggage_num, truck_num):
    """Return the minimum value of maximum load capacity of trucks."""
    left = max(baggage)
    right = sum(baggage)
    while left != right:
        mid = (left + right) // 2
        v = carriable_baggage(baggage, baggage_num, mid, truck_num)
        if v >= baggage_num:
            right = mid;
        else:
            left = mid
    return right


import sys

n, k = map(int, sys.stdin.readline().split())

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

P = min_capacity(T, n, k)

print(P)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil


def check_p(p):
    global k, ws
    ct, nt = 0, 1
    for w in ws:
        if ct + w <= p:
            ct += w
        else:
            nt += 1
            if nt > k:
                return False
            ct = w
    return True


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

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

p = max(ceil(sum(ws) / k), *ws)

while True:
    if check_p(p):
        break
    p += 1

print(p)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, raw_input().split())
T = []

for i in range(n):
  T.append(input())

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

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

  if j>=n:
    right = mid
  else:
    left = mid

print right

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, raw_input().split())
T = []

for i in range(n):
  T.append(input())

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

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

  if j>=n:
    right = mid
  else:
    left = mid

print right

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, raw_input().split())
T = []

for i in range(n):
  T.append(input())

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

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


  if j>=n:
    right = mid
  else:
    left = mid

print right

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

def allocate(k, w):
    t = [0] * k
    avg = math.ceil(1.0 * sum(w) / k)
    while True:
        maxp = p = i = 0
        for wi in w:
            p += wi
            if p > avg:
                p -= wi
                if p > maxp:
                    maxp = p
                p = wi
                i += 1

        if p > maxp:
            maxp = p

        if i < k and maxp <= avg:
            return maxp
            
        avg += 1

if __name__ == "__main__":
    w = sys.stdin.readlines()
    k = int(w[0].split()[1])
    del w[0]
    w = [int(wi) for wi in w]
    print allocate(k, w)

Submission status: Time Limit Exceeded

Solution code:

class Solve:
    def __init__(self):
        self.N, self.K = [int(i) for i in input().split()]
        self.W = [int(input()) for i in range(self.N)]

        self.a = max(self.W)-1  # >= 0; False
        self.b = sum(self.W)  # <= 10**9; True

    def check(self, P):
        k, p, W = 1, P, [w for w in self.W]
        while W:
            if p >= W[0]:
                p -= W.pop(0)
            elif k < self.K:
                k, p = k+1, P
            else:
                return False
        return True

    def solve(self):
        while self.b - self.a > 1:
            m = (self.a + self.b) // 2
            if self.check(m):
                self.b = m
            else:
                self.a = m
        return self.b

print(Solve().solve())

Submission status: Time Limit Exceeded

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

n, k = map(int, raw_input().split())
baggages = []
weight_sum = 0
for i in range(n):
    baggages.append(int(raw_input()))
for i in baggages:
    weight_sum += i
P_min = int(weight_sum/k)
tmp = P_min
while True:
    flag = True
    trucks = k-1
    i = 0
    while i < n:
        baggage = baggages[i]
        if P_min < baggage:
            P_min = baggage-1
            flag = False
            break
        if tmp >= baggage:
            tmp -= baggage
            i += 1
        else:
            tmp = P_min
            if trucks > 0:
                trucks -= 1
            else:
                flag = False
                break
    if flag:
        break
    else:
        P_min += 1
        tmp = P_min
print P_min

Submission status: Time Limit Exceeded

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

n, k = map(int, raw_input().split())
baggages = []
weight_sum = 0
for i in range(n):
    baggages.append(int(raw_input()))
for i in baggages:
    weight_sum += i
P_min = int(weight_sum/k)
for i in baggages:
    P_min = max(P_min, i)
tmp = P_min
while True:
    flag = True
    trucks = k-1
    i = 0
    while i < n:
        baggage = baggages[i]
        if tmp >= baggage:
            tmp -= baggage
            i += 1
        else:
            tmp = P_min
            if trucks > 0:
                trucks -= 1
            else:
                flag = False
                break
    if flag:
        break
    else:
        P_min += 1
        tmp = P_min
print P_min

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
n,k = list(map(int, input().split()))
k = min(n,k)
W = list(map(int,[input() for _ in range(n)]))
if k > 1: 
    P = 10001
    for b in combinations(range(1,n),k-1):
        s = 0
        Pi = 0
        for i in b:
            Pi = max(Pi, sum(W[s:i]))
            s = i
        P = min(P, max(Pi, sum(W[s:])))
    print(P)
else:
    print(sum(W))

Submission status: Time Limit Exceeded

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

ws = list(map(int, sys.stdin.read().split()))
h = sum(ws)
p = h // k


def isEnough(A, n, k, w):
    ps = [w for x in range(k)]
    j = 0
    for i in range(n):
        a = A[i]
        p = ps[j]
        if p < a:
            j += 1
            if j < k:
                p = ps[j]
            else:
                return False
        dif = p - a
        if dif < 0:
            return False
        else:
            ps[j] = dif
    return True

while not isEnough(ws, n, k, p):
    p += 1

print(p)

Submission status: Time Limit Exceeded

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

ws = list(map(int, sys.stdin.read().split()))
h = sum(ws)
p = h // k


def isEnough(A, n, k, w):
    one = w
    count = 0
    for a in A:
        if one < a:
            count += 1
            if count < k:
                one = w
            else:
                return False
        dif = one - a
        if dif < 0:
            return False
        else:
            one = dif
    return True

while not isEnough(ws, n, k, p):
    p += 1

print(p)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

num_list = [int(num) for num in sys.stdin.readlines()]
num_list.sort()
num_list.reverse()

amount = sum(num_list)/k

while True:
    used = []
    count = 0
    # print "amount = %d" % amount
    for idx1, num1 in enumerate(num_list):

        if idx1 in used:
            continue

        for idx2 in range(-1, len(num_list)*-1 + idx1, -1):
            if (len(num_list) + idx2) in used:
                continue

            if num1 + num_list[idx2] == amount:
                used.append(len(num_list) + idx2)
                used.append(idx1)
                count+=1
                # print "break(==) " + str(used)
                break
            elif num1 + num_list[idx2] > amount:
                used.append(idx1)
                count+=1
                # print "break(>) " + str(used)
                break
            else:
                used.append(len(num_list) + idx2)
                # print "continue " + str(used)
                continue

    if len(used) == len(num_list):
        break
    else:
        amount+=1

print amount

Submission status: Time Limit Exceeded

Solution code:
def cal(truck_num, cargos):
    p = []
    
    for i in range(len(cargos) - truck_num + 1):
        if truck_num > 1:
            p.append(max(sum(cargos[:i + 1]), cal(truck_num - 1, cargos[i + 1:])))
        else:
            return sum(cargos)
    return min(p)

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

def search_minimum_p_internal(lp, rp, k, ws):
    "?????????P????????????????????¢?´¢??????"
    cp = (lp + rp) // 2
    k1 = calc_k(cp, ws)
    if k1 == k:
        # ???????????¨????????????????°?????????¨???k??°????????????????????????
        return cp
    elif k1 < k:
        # ???????????¨???????????????k??°???????°?????????????????????§????????????????????????????????????
        return search_minimum_p_internal(lp, cp - 1, k, ws)
    else:
        # ???????????¨???????????????k??°????????????????????????????????????????????????????¶?????????????
        return search_minimum_p_internal(cp + 1, rp, k, ws)

def search_minimum_p(k, ws):
    """
    max(P) = max(wi) * max(n)
    ????????¨???????????????1??°?????¨????????????????????????
    min(P) = max(wi)
    ?°?????????¨??????????????????????????§????????????????????????????????????
    """
    maxp = 10000 * 100000
    minp = max(ws)
    p = search_minimum_p_internal(minp, maxp, k, ws)
    while True:
        k1 = calc_k(p - 1, ws)
        if k1 == k and p > minp:
            p -= 1
        else:
            return p

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

print(search_minimum_p(k, ws))

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:


global N,K
global ws

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

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

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

amin=0
amax=int(1E50)

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

Submission status: Time Limit Exceeded

Solution code:


global N,K
global ws

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

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

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

amin=0
amax=int(1E100)

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

Submission status: Time Limit Exceeded

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


def calc_minimum_payload(packets, num_of_trucks):
    num_of_packets = len(packets)
    p_max = packets[0]
    result = calc_allocatable_packet(packets, num_of_trucks, p_max)
    while result < num_of_packets:
        p_max += 1
        result = calc_allocatable_packet(packets, num_of_trucks, p_max)
    return p_max



if __name__ == '__main__':
    # ??????????????\???
    num_of_packets, num_of_trucks = [int(x) for x in input().split(' ')]
    packets = [int(input()) for _ in range(num_of_packets)]
    # packets = [8, 1, 7, 3, 9]

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

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

Submission status: Time Limit Exceeded

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


def get_ball_park_estimate(packets, num_of_trucks):
    num_of_packets = len(packets)
    upper_limit = 10000 * num_of_packets
    result = calc_allocatable_packet(packets, num_of_trucks, upper_limit)
    while result >= num_of_packets:
        upper_limit //= 2
        result = calc_allocatable_packet(packets, num_of_trucks, upper_limit)
    return upper_limit // 2, upper_limit


def calc_minimum_payload(packets, num_of_trucks):
    lower_limit, upper_limit = get_ball_park_estimate(packets, num_of_trucks)
    num_of_packets = len(packets)
    p_max = lower_limit
    result = calc_allocatable_packet(packets, num_of_trucks, p_max)
    while result < num_of_packets:
        p_max += 1
        result = calc_allocatable_packet(packets, num_of_trucks, p_max)
    return p_max

    #num_of_packets = len(packets)
    #p_max = packets[0]
    #result = calc_allocatable_packet(packets, num_of_trucks, p_max)
    #while result < num_of_packets:
    #    p_max += 1
    #    result = calc_allocatable_packet(packets, num_of_trucks, p_max)
    #return p_max



if __name__ == '__main__':
    # ??????????????\???
    num_of_packets, num_of_trucks = [int(x) for x in input().split(' ')]
    packets = [int(input()) for _ in range(num_of_packets)]
    # packets = [8, 1, 7, 3, 9]

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

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

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

# from random import randint
# n = 10000
# k = 100
w = [0 for _ in range(n)]
for i in range(n):
    w[i] = int(input())
    # w[i] = randint(1, 10000)
# print(w)
P = max(sum(w)//k, max(w))
count = 0
while True:
    m = 0
    ik = 1
    loss = max(w)
    for i in range(n):
        count += 1
        new = m + w[i]
        if new <= P:
            m = new
        else:
            loss = new - P if new - P < loss else loss
            m = w[i]
            ik += 1
            if ik > k:
                break
    if ik > k:
        # print("loss:", loss)
        P += loss
    else:
        break
            
        
print(P)
# print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

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

n, k = map(int, input().split())
w_i = [int(input()) for i in range(n)]
p_min = math.floor(sum(w_i) / k)
w_max = max(w_i)
if p_min < w_max:
    p_min = w_max
while not check_sekisairyo(k, p_min, w_i):
    p_min += 1
print(p_min)

Submission status: Time Limit Exceeded

Solution code:
def allocate(wl,n,k):
    maxw = max(wl)
    cap = maxw
    cp_k = k
    while True:
        for w in wl:
            cap = cap-w
            if cap<0:
                cap=maxw-w
                k-=1
        if k>0:
            break
        k = cp_k
        maxw += 1
        cap = maxw
    return maxw


def main():
    n,k = map(int,raw_input().split())
    wl = []
    for i in xrange(n):
        wl.append(input())
    ans = allocate(wl,n,k)
    print ans

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def allocate(wl,n,k):
    maxw = max(sum(wl)/k,max(wl))
    cap = maxw
    cp_k = k
    while True:
        for w in wl:
            cap = cap-w
            if cap<0:
                cap=maxw-w
                k-=1
        if k>0:
            break
        k = cp_k
        maxw += 1
        cap = maxw
    return maxw


def main():
    n,k = map(int,raw_input().split())
    wl = []
    for i in xrange(n):
        wl.append(input())
    ans = allocate(wl,n,k)
    print ans

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def get_min_p(offset, length, k, arr):
  if k == 1: return sum(arr[offset:offset + length])
  if k == 2:
    min_diff = float('inf')
    p = 0
    for i in range(1, length):
      a = sum(arr[offset:offset + i])
      b = sum(arr[offset + i:])
      if abs(a - b) < min_diff:
        min_diff = abs(a - b)
        p = max(a, b)
      #print("arr:{}, i:{}, p:{}".format(
      #  arr[offset:offset + length], i, p))
    return p
  else:
    e = len(arr) - k + 2
    p = [float('inf')] * e
    for i in range(1, e):
      #print("p:{}, i:{}".format(p, i))
      a = get_min_p(offset + i, length - i, k - 1, arr)
      b = sum(arr[offset:offset + i])
      p[i] = max(a, b)
    return min(p)

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

print(get_min_p(0, n, k, a))

Submission status: Time Limit Exceeded

Solution code:
p_list = {}

def get_min_p(offset, length, k, arr):
  key = "{}:{}".format(offset, k)
  if key in p_list: return p_list[key]

  if k == 1:
    p_list[key] = sum(arr[offset:offset + length])
  elif k == 2:
    min_diff = float('inf')
    p = 0
    for i in range(1, length):
      a = sum(arr[offset:offset + i])
      b = sum(arr[offset + i:])
      if abs(a - b) < min_diff:
        min_diff = abs(a - b)
        p = max(a, b)
      #print("arr:{}, i:{}, p:{}".format(
      #  arr[offset:offset + length], i, p))
    p_list[key] = p
  else:
    e = len(arr) - k + 2
    p = [float('inf')] * e
    for i in range(1, e):
      #print("p:{}, i:{}".format(p, i))
      a = get_min_p(offset + i, length - i, k - 1, arr)
      b = sum(arr[offset:offset + i])
      p[i] = max(a, b)
    p_list[key] = min(p)
  return p_list[key]

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

print(get_min_p(0, n, k, a))

Submission status: Time Limit Exceeded

Solution code:
import sys
n, k = map(int, input().split())
w = tuple(map(int, sys.stdin.readlines()))
p = max(w)
s = sum(w)
if n <= k:
    print(p)
elif k == 1:
    print(s)
else:
    a = max(p, s//k)
    while True:
        l = [a]
        for i in range(n):
            d = l[-1] - w[i]
            if d < 0:
                l.append(a-w[i])
            else:
                l[-1] = d
            i += 1
        if len(l) > k:
            a += 1
        else:
            break
    print(a)

Submission status: Time Limit Exceeded

Solution code:
def f(a,n,k,t):
    x=0
    for _ in [0]*k:
        s=0
        while s+t[x]<=a:
            s+=t[x];x+=1
            if(x>=n):return n
    else:return x

n,k=map(int,input().split())
t=[int(input()) for _ in [0]*n]
a=sum(t)//k
while f(a,n,k,t)!=n:a+=1
print(a)

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
w = [int(input()) for i in range(n)]
w.append(0)
w.reverse()
P = max((sum(w) // k) , max(w))
check = []
while True:
    x = w.copy()
    carcnt = 0
    while x != [0]:
        wgtcnt = 0
        while x[-1] != 0 and wgtcnt + x[-1] <= P:
            wgtcnt += x.pop()
        check.append(wgtcnt)
        carcnt += 1
    if carcnt <= k:
        print(P)
        break
    else:
        P += 1

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int,input().split())
weight = []
for i in range(n):
    weight.append(int(input()))
tmp_numberOfGroup = 0
tmp_p = max(weight) - 1
while tmp_numberOfGroup+1 != k:
    tmp_p += 1
    tmp_weight = 0
    tmp_numberOfGroup = 0
    for tmp_w in weight:
        if tmp_w+tmp_weight > tmp_p:
            tmp_numberOfGroup += 1
            tmp_weight = tmp_w
        else:
            tmp_weight += tmp_w

if k == 1:
    tmp_p = sum(weight)

print(tmp_p)

Submission status: Time Limit Exceeded

Solution code:
s = input().split(" ")
n = int(s[0])
k = int(s[1])
w = []
for i in range(n):
    w.append(int(input()))
mx = max(w)
while True:
    t = []
    t.append(w[0])
    for i in range(1,len(w)):
        if t[len(t)-1] + w[i] <= mx:
            t[len(t)-1] += w[i]
        else:
            t.append(w[i])
            if len(t) > k:
                break
    if len(t) > k:
        mx += 1
    else:
        break
print(mx)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil
s = input().split(" ")
n = int(s[0])
k = int(s[1])
w = []
total = 0
for i in range(n):
    a = int(input())
    w.append(a)
    total += a
mx = max(ceil(total / k), max(w))
while True:
    t = []
    t.append(w[0])
    for i in range(1,len(w)):
        if t[len(t)-1] + w[i] <= mx:
            t[len(t)-1] += w[i]
        else:
            t.append(w[i])
            if len(t) > k:
                break
    if len(t) > k:
        mx += 1
    else:
        break
print(mx)

Submission status: Time Limit Exceeded

Solution code:
#ALDS1_4-D Allocation

def pIsAccptbl(w,k,p):
    tr = 0
    c = 0
    while(w):
        tmp = w.pop(0)
        if( tr + tmp > p):
            tr = tmp
            c += 1
        else:
            tr += tmp

    c+=1
    if c>k:
        return False
    else:
        return True
    
n,k = input().split()
w=[]
for i in range(int(n)):
    t = int(input())
    w.append(t)

p = max(w)

while(1):
    x=w.copy()
    if(pIsAccptbl(x,int(k),p)):
        print(p)
        break
    else:
        p+=1

Submission status: Time Limit Exceeded

Solution code:
#ALDS1_4-D Allocation
from collections import deque

def pIsAccptbl(w,k,p):
    tr = 0
    c = 0
    while(w):
        tmp = w.popleft()
        if( tr + tmp > p):
            tr = tmp
            c += 1
        else:
            tr += tmp

    c+=1
    if c>k:
        return False
    else:
        return True
    
n,k = input().split()
w = []
for i in range(int(n)):
    w.append(int(input()))

p = max(w)

while(1):
    x=deque(w)
    if(pIsAccptbl(x,int(k),p)):
        print(p)
        break
    else:
        p+=1

Submission status: Time Limit Exceeded

Solution code:
#ALDS1_4-D Allocation
from collections import deque

def pIsAccptbl(w,k,p):
    tr = 0
    c = 0
    while(w):
        tmp = w.popleft()
        if( tr + tmp > p):
            tr = tmp
            c += 1
        else:
            tr += tmp
        if c+1>k:return False
    return True
    
n,k = input().split()
w = []
for i in range(int(n)):
    w.append(int(input()))

p = max(w)

while(1):
    x=deque(w)
    if(pIsAccptbl(x,int(k),p)):
        print(p)
        break
    else:
        p+=1

Submission status: Time Limit Exceeded

Solution code:
#ALDS1_4-D Allocation
from collections import deque

def pIsAccptbl(w,k,p):
    tr = 0
    c = 0
    while(w):
        tmp = w.popleft()
        if(tmp > p):return False
        if( tr + tmp > p):
            tr = tmp
            c += 1
        else:
            tr += tmp
        if c+1>k:return False
    return True
    
n,k = [int(x) for x in input().split()]
w = []
for i in range(n):
    w.append(int(input()))

p = int(sum(w)/k)+1
if(sum(w)%k==0):p-=1
while(1):
    x=deque(w)
    if(pIsAccptbl(x,k,p)):
        print(p)
        break
    else:
        p+=1

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def cndP(l,n,p1,p2):
    d = set()
    min = sum(l[:])
    length = len(l)
    for i in range(length-n+1):
        s = sum(l[i:i+n])
        if s < min:
            min = s
        if p2 == None:
            if p1 < s:
                d.add(s)
        else:
            if p1 < s < p2:
                d.add(s)
    d.add(min)
    return sorted(d)

def pIsAccptbl(w,k,p):
    tr = 0
    c = 0
    d = deque(w)
    while(d):
        tmp = d.popleft()
        if(tmp > p):
            return False
        
        if( tr + tmp > p):
            tr = tmp
            c += 1
        else:
            tr += tmp
        if c+1>k:
            return False
    return True

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

p = max(w)

if(pIsAccptbl(w,k,p)):
    print(p)
else:
    n=2
    p1 = p
    p2 = None
    while(1):
        s = cndP(w,n,p1,p2)
        if not p2 == None:
            if s[0] > p2:
                print(p2)
                break;
        for i in s:
            if(pIsAccptbl(w,k,i)):
                p2 = i
                break
            if(p2==None):
                p1 = i
        n+=1