結果

問題 No.1211 円環はお断り
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 19:13:08
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,276 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 400 ms
コンパイル使用メモリ 82,616 KB
実行使用メモリ 94,868 KB
最終ジャッジ日時 2025-06-12 19:13:14
合計ジャッジ時間 5,434 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other AC * 13 TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import bisect

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

    def is_possible(M):
        if M == 0:
            return True
        S = sum(A)
        if S < K * M:
            return False

        # Check linear split
        cnt = 0
        current_sum = 0
        for num in A:
            current_sum += num
            if current_sum >= M:
                cnt += 1
                current_sum = 0
        if cnt >= K:
            return True

        # Precompute prefix sums
        n = len(A)
        pre_sum = [0] * (n + 1)
        for i in range(n):
            pre_sum[i+1] = pre_sum[i] + A[i]

        # Precompute suffix sums
        suf_sum = [0] * (n + 1)
        for i in range(n-1, -1, -1):
            suf_sum[i] = suf_sum[i+1] + A[i]

        # Check each possible i for wrapping around
        for i in range(n):
            s = suf_sum[i]
            need = M - s
            if need <= 0:
                # j is -1, start=0, end=i-1
                start = 0
                end = i - 1
            else:
                # Find smallest j where pre_sum[j+1] >= need
                j_plus_1 = bisect.bisect_left(pre_sum, need)
                if j_plus_1 > n:
                    continue  # no such j
                start = j_plus_1
                end = i - 1

            if start > end:
                continue  # no elements in the remaining part

            # Calculate how many splits in [start, end]
            current = 0
            current_sum = 0
            for k in range(start, end + 1):
                current_sum += A[k]
                if current_sum >= M:
                    current += 1
                    current_sum = 0
            if current >= K - 1:
                return True

        return False

    # Binary search
    left = 0
    right = sum(A) // K
    answer = 0
    while left <= right:
        mid = (left + right) // 2
        if is_possible(mid):
            answer = mid
            left = mid + 1
        else:
            right = mid - 1
    print(answer)

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