結果

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

ソースコード

diff # 

def max_min_value():
    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

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

    while low <= high:
        mid = (low + high) // 2

        # Compute max_linear
        max_linear = 0
        current_sum = 0
        left = 0
        right = 0
        cnt_linear = 0
        while right < N:
            current_sum += A[right]
            if current_sum >= mid:
                cnt_linear += 1
                current_sum = 0
                left = right + 1
                right = left
            else:
                right += 1
        max_linear = cnt_linear

        if max_linear >= K:
            best = mid
            low = mid + 1
        else:
            if S < mid * K:
                high = mid - 1
            else:
                B = A + A
                prefix_b = [0] * (2 * N + 1)
                for i in range(2 * N):
                    prefix_b[i + 1] = prefix_b[i] + B[i]
                found = False
                for i in range(N):
                    left = i
                    right = i
                    cnt = 0
                    while right < i + N:
                        sum_ = prefix_b[right + 1] - prefix_b[left]
                        if sum_ >= mid:
                            cnt += 1
                            left = right + 1
                            right = left
                        else:
                            right += 1
                    if cnt >= K:
                        found = True
                        break
                if found:
                    best = mid
                    low = mid + 1
                else:
                    high = mid - 1

    print(best)

max_min_value()
0