結果

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

ソースコード

diff #
raw source code 

def max_m():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:2+N]))
    
    def is_possible(M):
        total = sum(A)
        if total < M * K:
            return False
        B = A + A
        pre_sum = [0] * (2 * N + 1)
        for i in range(2 * N):
            pre_sum[i+1] = pre_sum[i] + B[i]
        
        split_pos = [-1] * (2 * N)
        j = 0
        for i in range(2 * N):
            while j < 2 * N and pre_sum[j+1] - pre_sum[i] < M:
                j += 1
            if j < 2 * N:
                split_pos[i] = j + 1
            else:
                split_pos[i] = -1
        
        for i in range(N):
            current = i
            count = 0
            for _ in range(K):
                if current == -1:
                    break
                if split_pos[current] == -1:
                    current = -1
                    break
                if split_pos[current] > i + N:
                    current = -1
                    break
                count += 1
                current = split_pos[current]
            if count >= K:
                return True
        return False
    
    left = 0
    right = sum(A)
    best = 0
    while left <= right:
        mid = (left + right) // 2
        if is_possible(mid):
            best = mid
            left = mid + 1
        else:
            right = mid - 1
    print(best)

max_m()
0