提出 #31263600

---

ソースコード 拡げる

def solve():
    INF = 1000000000000000000
    n, k = map(int, input().split())
    a = [int(input()) for i in range(n)]
    s = [a[0]] * n # a の累積和
    for i in range(n - 1):
        s[i + 1] = s[i] + a[i + 1]
    if s[-1] == k:
        print(1) # コーナーケース
        return

    dp = [[INF] * (n + 1) for i in range(n)]
    # dp[i][j] = i 日目までに j 日機嫌が良くなるために必要な勝利回数の最小値
    dp[0][0] = 0
    dp[0][1] = 1
    for i in range(1, n):
        for j in range(n + 1):
            dp[i][j] = dp[i - 1][j]
            if j > 0:
                # i 日目に機嫌を良くすることを考える
                # i - 1 日目までの勝率は dp[i - 1][j - 1] / s[i - 1]
                # 今日の勝利回数を x として i - 1 日目までの勝率を超えるには
                # dp[i - 1][j - 1] / s[i - 1] < x / a[i]
                # x > (dp[i - 1][j - 1] * a[i - 1]) / s[i - 1]
                x = (dp[i - 1][j - 1] * a[i]) // s[i - 1] + 1
                dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + x)
    answer = 0
    for i in range(n + 1):
        if dp[n - 1][i] <= k:
            answer = i
    print(answer)
solve()

提出情報

ジャッジ結果