Codeforces Round #307(Div. 2) - C. GukiZ hates Boxes

cdf307_2c.py

def check(time):
    # time以下に箱を取り除けるか
    box = A[:]
    now = last
    for student in range(m):
        rest = time - now - 1 # 移動時間を引いた、残りの行動可能な時間
        if rest <= 0:
            # 移動できない(もしくは移動しかできない)ときはダメ
            return False
        while now >= 0 and rest >= 0:
            # 残り時間がある限り、後ろから箱を取り除いていく
            if box[now] <= rest:
                rest -= box[now]
                now -= 1
            else:
                box[now] -= rest
                break
        if now == -1:
            # 全て取り除けていれば成功
            return True
    return False

n, m = map(int, input().split())
A = list(map(int, input().split()))
last = n-1
while A[last] == 0:
    last -= 1

low, high = 1, n + sum(A) + 1
while high - low > 1:
    mid = (high + low) // 2
    if check(mid) == False:
        low = mid
    else:
        high = mid
print(high)