結果

問題 No.1211 円環はお断り
コンテスト
ユーザー qwewe
提出日時 2025-05-14 12:52:31
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,304 bytes
コンパイル時間 406 ms
コンパイル使用メモリ 82,240 KB
実行使用メモリ 107,648 KB
最終ジャッジ日時 2025-05-14 12:54:27
合計ジャッジ時間 5,473 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 36 WA * 5
権限があれば一括ダウンロードができます

ソースコード

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]))
    sum_A = sum(A)
    if K == 0:
        print(0)
        return
    
    def is_possible(M):
        if sum_A < K * M:
            return False
        
        # Check if linear split is possible
        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
        if cnt >= K:
            return True
        
        # Try merging first and last segments
        # Find first segment
        s1 = 0
        first_end = -1
        current_sum = 0
        for i in range(N):
            current_sum += A[i]
            if current_sum >= M:
                s1 = current_sum
                first_end = i
                break
        else:
            return False  # Cannot form first segment
        
        # Find last segment
        s2 = 0
        last_start = N
        current_sum = 0
        for j in range(N-1, -1, -1):
            current_sum += A[j]
            if current_sum >= M:
                s2 = current_sum
                last_start = j
                break
        else:
            return False  # Cannot form last segment
        
        # Check overlap
        if first_end >= last_start:
            return False
        
        # Check sum of mid part
        sum_mid = sum_A - s1 - s2
        if sum_mid < (K-1)*M:
            return False
        
        # Check mid part can be split into K-1 segments
        current_sum = 0
        cnt_mid = 0
        for num in A[first_end+1:last_start]:
            current_sum += num
            if current_sum >= M:
                cnt_mid += 1
                current_sum = 0
                if cnt_mid >= K-1:
                    break
        return cnt_mid >= K-1
    
    left = 1
    right = sum_A // K
    ans = 0
    while left <= right:
        mid = (left + right) // 2
        if is_possible(mid):
            ans = mid
            left = mid + 1
        else:
            right = mid - 1
    print(ans)

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