結果

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

ソースコード

diff #
raw source code 

n, k = map(int, input().split())
a = list(map(int, input().split()))

def is_possible(m):
    total = sum(a)
    if total < m * k:
        return False
    cnt = 0
    current = 0
    for num in a:
        current += num
        if current >= m:
            cnt += 1
            current = 0
    if cnt >= k:
        return True
    # Check if there exists a wrap-around segment
    prefix = []
    s = 0
    for num in a:
        s += num
        prefix.append(s)
    suffix = []
    s = 0
    for num in reversed(a):
        s += num
        suffix.append(s)
    suffix = suffix[::-1]
    # Find earliest prefix >= m
    earliest_prefix = None
    for i in range(n):
        if prefix[i] >= m:
            earliest_prefix = i + 1  # 1-based index
            break
    if earliest_prefix is None:
        return False
    # Find earliest suffix >= m
    earliest_suffix = None
    for i in range(n-1, -1, -1):
        if suffix[i] >= m:
            earliest_suffix = i + 1  # 1-based index
            break
    if earliest_suffix is None:
        return False
    # Check if there's a valid combination
    # The middle part is from earliest_prefix to earliest_suffix - 2 (0-based)
    if earliest_prefix >= earliest_suffix:
        return False
    middle = a[earliest_prefix:earliest_suffix-1]
    current = 0
    middle_cnt = 0
    for num in middle:
        current += num
        if current >= m:
            middle_cnt += 1
            current = 0
    return middle_cnt >= k - 2

low = 0
high = sum(a)
ans = 0
while low <= high:
    mid = (low + high) // 2
    if is_possible(mid):
        ans = mid
        low = mid + 1
    else:
        high = mid - 1
print(ans)
0