結果

問題 No.1211 円環はお断り
ユーザー gew1fw
提出日時 2025-06-12 17:08:52
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,915 bytes
コンパイル時間 339 ms
コンパイル使用メモリ 82,620 KB
実行使用メモリ 96,192 KB
最終ジャッジ日時 2025-06-12 17:08:58
合計ジャッジ時間 4,833 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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

    if K ==0:
        print(0)
        return
    
    total = sum(A)
    low = 0
    high = total // K
    best = 0

    def is_possible(M):
        if M ==0:
            return True
        if K * M > total:
            return False
        S_prime = A + A
        pre_sum = [0] * (2*N +1)
        for i in range(2*N):
            pre_sum[i+1] = pre_sum[i] + S_prime[i]
        jump = [0]*(2*N +2)
        for i in range(2*N):
            left = i+1
            right = 2*N
            res = 2*N +1
            while left <= right:
                mid = (left + right) //2
                if pre_sum[mid] - pre_sum[i] >= M:
                    res = mid
                    right = mid -1
                else:
                    left = mid +1
            jump[i] = res if res <=2*N else -1
        for i_start in range(N):
            window_end = i_start + N
            if window_end > 2*N:
                break
            sum_window = pre_sum[window_end] - pre_sum[i_start]
            if sum_window < K * M:
                continue
            current = i_start
            count =0
            for _ in range(K):
                next_pos = jump[current]
                if next_pos == -1 or next_pos > window_end:
                    break
                current = next_pos
                count +=1
            if count >= K and current <= window_end:
                if pre_sum[window_end] - pre_sum[i_start] >= K * M:
                    return True
        return False

    while low <= high:
        mid = (low + high) //2
        if is_possible(mid):
            best = mid
            low = mid +1
        else:
            high = mid -1
    print(best)

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