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:
import sys
import math

def check(k, w, P):
    i = 0
    for t in range(k):
        p = 0
        while p + w[i] < P:
            p += w[i]
            i += 1
            if i == len(w):
                return True
    return False

def allocate(k, w):
    t = [0] * k
    le = 0
    ri = 100000 * 10000

    while ri - le > 0:
        P = (ri + le) / 2
        if check(k, w, P):
            ri = P - 1
        else:
            le = P + 1
    return ri

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

Solution code:
N, K = [int(s) for s in raw_input().split()]
ws = [int(raw_input()) for _ in xrange(N)]
lo, hi = max(ws), sum(ws)

while hi - lo > 1:
    p = P = (lo + hi) / 2
    k = 1
    for w in ws:
        if w > p:
            p = P
            k += 1
        p -= w
    if k <= K:
        hi = P
    else:
        lo = P

print hi

Submission status: Wrong Answer

Solution code:
import math
sum1 = 0 
n,k = map(int,input().split())
arr = []
for i in range(n):
	arr.append(input())
for num in arr:
	sum1 += int(num)
min = sum1/k
print(math.ceil(min))

Submission status: Wrong Answer

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

capa = w[:k]

for i in range(k, n):
    capa[capa.index(min(capa))] += w[i]

print(max(capa))

Submission status: Wrong Answer

Solution code:

# ?????§?????????P???K??°?????????????????§???????????????????????????????
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


def solve():
    left = 0
    right = max(w) + 1  # ??????????????°???* 1????????????????????§??????
    while right - left > 1:
        mid = (left + right) / 2
        v = check(mid)  # mid == P ??¨???????????§???????????????????????????
        if v >= n:
            right = mid
        else:
            left = mid

    return right

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

Submission status: Wrong Answer

Solution code:

# ?????§?????????P???K??°?????????????????§???????????????????????????????
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


def solve():
    left = 0
    right = sum(w) + 1 # ??????????????°???* 1????????????????????§??????
    while right - left > 1:
        mid = (left + right) / 2
        v = check(mid)  # mid == P ??¨???????????§???????????????????????????
        if v >= n:
            right = mid
        else:
            left = mid
        print(left, right)

    return right

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

Submission status: Wrong Answer

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

# temporary limit of a trug
limit = sum(w)/k

# put the items for a trug tentatively
trug = [0 for i in xrange(k)]
i = 0
for j in xrange(k-1):
    t = 0
    while t < limit:
        t += w[i]
        i += 1
    trug[j] = t
# the last trug
trug[k-1] = sum(w[i:])

# output
print max(trug)

Submission status: Wrong Answer

Solution code:
def moveRight(trug, start, stop):
    if trug[start][1]-trug[start][0] > 1:
        for i in xrange(stop-start):
            trug[start+i][1] -= 1
            trug[start+i+1][0] -= 1

def moveLeft(trug, start, stop):
    if trug[start][1]-trug[start][0] > 1:
        for i in xrange(start-stop):
            trug[start-i][0] += 1
            trug[start-i-1][1] += 1

def calcWeight(trug, w):
    temp = [ sum(w[trug[i][0]:trug[i][1]]) for i in xrange(len(trug)) ]
    return temp

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

if k == 1:
    trug = [[0, n]]
else:
    ta = n/k
    trug = [[i*ta, ta+i*ta] for i in xrange(k-1)]
    trug.append([(i+1)*ta, n])

trugw = calcWeight(trug, w)
maxt  = max(trugw)
imaxt = trugw.index(maxt)
mint  = min(trugw)
imint = trugw.index(mint)

while True:
    if   imaxt == imint:
        break
    elif imaxt < imint:
        if mint+w[trug[imint-1][1]-1] < maxt:
            moveRight(trug, imaxt, imint)
    else:
        if mint+w[trug[imint+1][0]] < maxt:
            moveLeft(trug, imaxt, imint)
    
    trugw = calcWeight(trug, w)
    n = max(trugw)
    if n >= maxt:
        break
    else:
        maxt  = n
        imaxt = trugw.index(maxt)
        mint = min(trugw)
        imint = trugw.index(mint)

print maxt

Submission status: Wrong Answer

Solution code:
n0, n1 = input().split()

t = []
for i in range(int(n0)):
    t.append(int(input()))
min = (sum(t) // int(n1)) + (sum(t) % int(n1))
print(min)

Submission status: Wrong Answer

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


def binarysearch(start, end):
    left = start
    right = end
    mid = 0

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


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

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

Submission status: Wrong Answer

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


def binarysearch(start, end):
    left = start
    right = end
    mid = 0

    while left < right:
        mid = (left + right)//2
        print(mid)
        if simulate(mid, w, k):
            right = mid
            print("ok")
        else:
            mid += 1
            left = mid
    return mid


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

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

Submission status: Wrong Answer

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

ws = list(map(int, sys.stdin.read().split()))

M = 100000000000
for i in range(0, n):
    for j in range(i, n):
        m = max(sum(ws[0:i]), sum(ws[i:j]), sum(ws[j:n]))
        M = min(m, M)

print(M)

Submission status: Wrong Answer

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

wlist = [int(num) for num in sys.stdin.readlines()]

wlist.sort()
wlist.reverse()

sum=0
for w in wlist:
    sum += w

ave=sum/len(wlist)

used=[]
i=0
while True:

    count=0
    used = []
    for idx, w in enumerate(wlist):

        if (len(wlist)*-1 + idx) in used:
            continue
        if w > ave:
            break
        sum = w
        for x in range(-1, len(wlist)*-1 + idx, -1):
            if x in used:
                continue
            if sum + wlist[x] == ave:
                used.append(x)
                used.append(len(wlist)*-1 + idx)
                count += 1
                break
            if sum + wlist[x] > ave:
                count += 1
                used.append(len(wlist)*-1 + idx)
                break
    
            sum += wlist[x]
            used.append(x)
        else:
            used.append(len(wlist)*-1 + idx)
            count += 1
            
    if count <= k and len(used)==len(wlist):
        break
    else:
        ave += 1

print ave

Submission status: Wrong Answer

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

print str(num_list)

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

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

# print str(num_list)
# print amount

i = 0
while True:

    if i > 5:
        break
    i+=1
    used = []
    count = 0
    # print "amount = %d" % amount
    for idx1, num1 in enumerate(num_list):

        if idx1 in used:
            continue
        
        if num1 > amount:
            break

        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
        else:
            used.append(idx1)

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

print amount

Submission status: Wrong Answer

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

# print str(num_list)
# print amount

while True:

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

        if idx1 in used:
            continue
        
        if num1 > amount:
            break

        is_append = False
        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)
                count+=1
                # print "break(==) " + str(used)
                is_append = True
                break
            elif num1 + num_list[idx2] > amount:
                count+=1
                # print "break(>) " + str(used)
                is_append = True
                break
            else:
                used.append(len(num_list) + idx2)
                # print "continue " + str(used)
                is_append = True
                continue

        # print is_append
        if is_append:
            # print "eixt space"
            used.append(idx1)

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

print amount

Submission status: Wrong Answer

Solution code:
#coding:UTF-8
def Check(P,k,w):
    i=0
    for j in range(k):
        s=0
        while s+w[i]<=P:
            s+=w[i]
            i+=1
            if i==n:
                return n
    return i

def Allocation(n,k,w):
    left=0
    right=100000
    while right-left > 1:
        mid=int((left+right)/2)
        v=Check(mid,k,w)
        if v>=n:
            right=mid
        else:
            left=mid
    print(right)
  
if __name__=="__main__":
    a=input()
    n=int(a.split(" ")[0])
    k=int(a.split(" ")[1])
    w=[]
    for i in range(n):
        w.append(int(input()))
    Allocation(n,k,w)

Submission status: Wrong Answer

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(1,len(cargos) - truck_num + 1):
        if not i == 1 and p < sum(cargos[:i]):
            continue
        if truck_num > 1:
            r = max(sum(cargos[:i]), cal(truck_num - 1, cargos[i:]))
            if i == 1:
                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: Wrong Answer

Solution code:
# encoding: utf-8


import sys
import math


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

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

        weight_list = list(map(int, self.__input[1:]))

        assert product_num == len(weight_list)
        print(product_num, truck_num, weight_list)

        truck_capacity = max(math.ceil(sum(weight_list) / truck_num), max(weight_list))

        return str(truck_capacity)

        #     for each in array_2:
        #         if self.allocation(key=each, array=weight_list, array_length=max(weight_list)):
        #             truck_capacity += 1
        #
        #     return str(truck_capacity)
        #
        # @staticmethod
        # def allocation(key, array, array_length):
        #     # print(len(set(array_1).intersection(set(array_2))))
        #     left, right = max(array), array_length
        #     while left < right:
        #         mid = (left + right) // 2
        #         if key == array[mid]:
        #             return True
        #         elif key < array[mid]:
        #             right = mid
        #         else:
        #             left = mid + 1
        #     return False


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

Submission status: Wrong Answer

Solution code:
# encoding: utf-8


import sys
import math


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

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

        weight_list = list(map(int, self.__input[1:]))

        assert product_num == len(weight_list)
        # print(product_num, truck_num, weight_list)

        truck_capacity = max(math.ceil(sum(weight_list) / truck_num), max(weight_list))

        return str(truck_capacity)

        #     for each in array_2:
        #         if self.allocation(key=each, array=weight_list, array_length=max(weight_list)):
        #             truck_capacity += 1
        #
        #     return str(truck_capacity)
        #
        # @staticmethod
        # def allocation(key, array, array_length):
        #     # print(len(set(array_1).intersection(set(array_2))))
        #     left, right = max(array), array_length
        #     while left < right:
        #         mid = (left + right) // 2
        #         if key == array[mid]:
        #             return True
        #         elif key < array[mid]:
        #             right = mid
        #         else:
        #             left = mid + 1
        #     return False


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

Submission status: Wrong Answer

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

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

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

    return None

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

print(search_minimum_p(k, ws))

Submission status: Wrong Answer

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

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

def test(truck_num, carogs):
    total = sum(carogs)
    remain = total % truck_num
    average = int(total / truck_num)
    if remain == 0:
        return average
    else:
        return average + 1
    
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(test(truck_num,cargos))

Submission status: Wrong Answer

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

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

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

def solve(truck_num, cargs):

    max_load = sum(cargos)
    min_load = max(cargos)

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

    return target_load

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

Submission status: Wrong Answer

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

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

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

def solve(truck_num, cargs):

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

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

Submission status: Wrong Answer

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

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

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

def solve(truck_num, cargs):

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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:
                tmp = sum(w[i:])//k
                loss = tmp if tmp > loss else loss 
                break
    if ik > k:
        # print("loss:", loss)
        P += loss
    else:
        break
            
        
print(P)
# print(count)

Submission status: Wrong Answer

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)
while not check_sekisairyo(k, p_min, w_i):
    p_min += 1
print(p_min)

Submission status: Wrong Answer

Solution code:
def allocate(wl,n,k):
    maxw = max(wl)
    sumw = sum(wl)
    while maxw*k < sumw:
        maxw+=1
    print maxw

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def allocate(wl,n,k):
    maxw = sum(wl)/k
    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: Wrong Answer

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


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

Solution code:
def allocate(wl,n,k):
    avew = sum(wl)/k
    maxw = max(wl)
    limit = max(avew,maxw)
    cap = limit
    cp_k = k
    span = 100
    # span = 1
    # print limit
    while True:
        # time.sleep(1)
        # print "limit:",limit
        for w in wl:
            cap = cap-w
            if cap<0:
                cap=limit-w
                k-=1
                # print "k:",k
        limit += span
        cap = limit
        if span==1 and k>0 and not cap<maxw:
            break
        if span>0 and k>0:
            span = -span/10
        if span<0 and k<=0:
            span = -span/10
        k = cp_k
        # print limit
    return limit


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

Solution code:
import sys
import math

def is_capable(n, k, w, P):
    track = 0
    cnt = 0
    i = 0

    while cnt < k:
        if i == n:
            return True

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

    return False
    pass

# ??\?????¨
n, k = map(int, sys.stdin.readline().split())
w = []
for i in range(n):
    w.append(int(sys.stdin.readline().strip()))

'''
print(n,k)
print(w)
'''

# ????????¨

if k == 1:
    ans = sum(w)
    print(ans)
elif n == 1:
    ans = w[0]
    print(ans)
else:
    max_p = sum(w)
    min_p = math.ceil(max_p / k) - 1

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

    capable = {min_p:False, max_p:True}

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

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

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

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

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

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

    print(ans)
    print(capable)

Submission status: Wrong Answer

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

a = sorted([int(input()) for i in range(n)], reverse=True)
track = [0] * k

for i in a:
  track[track.index(min(track))] += i
print(max(track))

Submission status: Wrong Answer

Solution code:
def get_min_p(offset, length, k, arr):
  if k == 1: return sum(arr[offset:offset + length])
  if k == 2:
    min_diff = 100
    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:
    p = [100] * (len(arr) - k + 2)
    for i in range(1, len(arr) - k + 2):
      #print("p:{}, i:{}".format(p, i))
      a = get_min_p(offset + i, length - i, k - 1, arr)
      b = sum(arr[: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))