結果

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

ソースコード

diff #
raw source code 

import sys

def main():
    import sys
    sys.setrecursionlimit(1 << 25)
    N, K = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    if K == 0:
        print(0)
        return
    total = sum(A)
    if total < K:
        print(0)
        return

    def can_split(M):
        if M == 0:
            return True
        total_needed = K * M
        if total < total_needed:
            return False
        A_double = A + A
        n = len(A_double)
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i+1] = prefix[i] + A_double[i]
        next_jump = [n] * (n + 1)
        for i in range(n + 1):
            low = i + 1
            high = n
            res = n
            while low <= high:
                mid = (low + high) // 2
                if prefix[mid] - prefix[i] >= M:
                    res = mid
                    high = mid - 1
                else:
                    low = mid + 1
            next_jump[i] = res
        for i in range(N):
            window_end = i + N
            if prefix[window_end] - prefix[i] < total_needed:
                continue
            current = i
            count = 0
            while True:
                if current >= window_end:
                    break
                next_p = next_jump[current]
                if next_p > window_end:
                    break
                current = next_p
                count += 1
            if count >= K:
                return True
        return False

    low = 0
    high = (total + K - 1) // K  # 最大可能的M
    answer = 0
    while low <= high:
        mid = (low + high) // 2
        if can_split(mid):
            answer = mid
            low = mid + 1
        else:
            high = mid - 1
    print(answer)

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