結果

問題 No.1211 円環はお断り
ユーザー gew1fw
提出日時 2025-06-12 21:48:09
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,651 bytes
コンパイル時間 283 ms
コンパイル使用メモリ 82,196 KB
実行使用メモリ 95,700 KB
最終ジャッジ日時 2025-06-12 21:54:31
合計ジャッジ時間 5,907 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other AC * 13 TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    K = int(input[idx])
    idx += 1
    A = list(map(int, input[idx:idx+N]))
    idx += N

    total = sum(A)
    if K == 0:
        print(0)
        return
    if K == 1:
        print(total)
        return

    def is_possible_linear(M):
        current = 0
        cnt = 0
        for num in A:
            current += num
            if current >= M:
                cnt += 1
                current = 0
        return cnt >= K

    def is_possible_circular(M):
        B = A + A
        n = len(B)
        pre_sum = [0] * (n + 1)
        for i in range(n):
            pre_sum[i+1] = pre_sum[i] + B[i]

        max_possible = 0
        for i in range(N):
            j = i
            current = 0
            cnt = 0
            while j < i + N:
                current += B[j]
                if current >= M:
                    cnt += 1
                    current = 0
                j += 1
            max_possible = max(max_possible, cnt)
            if max_possible >= K:
                return True
        return max_possible >= K

    low = 0
    high = total // K
    best = 0
    while low <= high:
        mid = (low + high) // 2
        if mid == 0:
            best = 0
            low = mid + 1
            continue
        if is_possible_linear(mid):
            best = mid
            low = mid + 1
        else:
            if is_possible_circular(mid):
                best = mid
                low = mid + 1
            else:
                high = mid - 1
    print(best)

if __name__ == "__main__":
    main()
0