結果

問題 No.1211 円環はお断り
ユーザー qwewe
提出日時 2025-05-14 13:25:40
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 5,310 bytes
コンパイル時間 171 ms
コンパイル使用メモリ 82,976 KB
実行使用メモリ 262,780 KB
最終ジャッジ日時 2025-05-14 13:27:08
合計ジャッジ時間 40,322 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 33 TLE * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def solve():
    N, K = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))

    if N == 0: # Based on constraints 1 <= K <= N, N cannot be 0.
        print(0)
        return

    A_double = A + A
    
    # Max K is N (10^5). log2(10^5) approx 16.6.
    # So, we need powers up to 2^16 (dp table rows 0 to 16). Size 17.
    # LOG_MAX_K_CONST determines number of rows in dp table.
    LOG_MAX_K_CONST = 18 # Sufficient for K up to 2^17-1. Covers K <= 10^5.

    # infinity_val indicates a pointer beyond A_double or failure to form segment.
    # A_double indices are 0 to 2*N-1.
    # next_start[j] can be 2*N if segment A[j...2*N-1] is valid, and next starts "at" 2*N.
    # Or 2*N if no segment can be formed.
    infinity_val = 2 * N 

    # memo_can_check = {} # Optional: memoization for can() if N is small, but not needed here.

    def can(m_test):
        # if m_test in memo_can_check: return memo_can_check[m_test]

        # 1. Calculate next_start array using two pointers.
        # next_s[j] = p, where segment A_double[j...p-1] has sum >= m_test, and p is smallest such.
        # p is the exclusive end index (start of the next segment).
        # If no such segment, p = infinity_val.
        next_s = [infinity_val] * (2 * N)
        
        current_sum = 0
        right_ptr = 0 # Exclusive end of the current window [left_ptr, right_ptr)
        for left_ptr in range(2 * N):
            # Expand window to the right until sum >= m_test or end of A_double
            while right_ptr < 2 * N and current_sum < m_test:
                current_sum += A_double[right_ptr]
                right_ptr += 1
            
            if current_sum >= m_test:
                next_s[left_ptr] = right_ptr 
            # else: next_s[left_ptr] remains infinity_val (initialized)
            
            # Shrink window from the left for the next iteration
            # current_sum is for window [left_ptr, right_ptr)
            # For next iteration (left_ptr+1), sum will be for [left_ptr+1, right_ptr)
            current_sum -= A_double[left_ptr]
            # If A_double[left_ptr] was very large, current_sum could become negative.
            # However, A_i >= 1, so this won't make sum negative unless m_test itself is strange.
            # No need for `if current_sum < 0: current_sum = 0` if A_i positive.

        # 2. Build DP table for jumps (binary lifting)
        # dp[k][i] = end position (start of next segment) after 2^k segments, starting from i.
        # dp table dimensions: LOG_MAX_K_CONST rows, 2*N + 1 columns (for index 2*N = infinity_val)
        dp = [[infinity_val] * (2 * N + 1) for _ in range(LOG_MAX_K_CONST)]

        # Base case: dp[0][i] is one jump
        for i in range(2 * N):
            dp[0][i] = next_s[i]
        dp[0][infinity_val] = infinity_val # dp[0][2*N] = 2*N, ensures infinity propagates

        # Fill DP table
        for k_power in range(1, LOG_MAX_K_CONST):
            for i in range(2 * N + 1): # Iterate up to 2*N (infinity_val index)
                intermediate_pos = dp[k_power-1][i]
                # intermediate_pos will be an index from 0 to 2*N.
                # dp[k_power-1] is defined for all these indices.
                dp[k_power][i] = dp[k_power-1][intermediate_pos]
        
        # 3. Check for each starting position s in the original circle
        for s_original_idx in range(N): # s_original_idx is the start in A_double as well
            current_pos = s_original_idx 
            
            # Perform K jumps using the DP table
            temp_K = K
            for k_bit_idx in range(LOG_MAX_K_CONST):
                if (temp_K >> k_bit_idx) & 1: # If 2^(k_bit_idx) is part of K
                    current_pos = dp[k_bit_idx][current_pos]
                # If current_pos becomes infinity_val, it will stay infinity_val
                # due to dp[...][infinity_val] = infinity_val.

            # After K jumps, current_pos is the start of the (K+1)-th segment.
            # The K segments are A_double[s_original_idx ... current_pos-1].
            # Total number of beads used = current_pos - s_original_idx.
            # We need this to be at most N.
            # This condition also implicitly checks if current_pos < infinity_val,
            # because if current_pos = infinity_val (2*N), then 2*N - s_original_idx <= N
            # implies N <= s_original_idx, which is false since s_original_idx < N.
            if (current_pos - s_original_idx) <= N:
                # memo_can_check[m_test] = True
                return True
        
        # memo_can_check[m_test] = False
        return False

    # Binary search for M
    low = 1
    # Max possible M is sum of all A's (for K=1). Max sum A_i = 10^9, N=10^5 => sum ~ 10^14.
    high = 0
    for x_val in A: high += x_val 
    
    ans = 0 # Stores the maximum M found so far.

    while low <= high:
        mid = low + (high - low) // 2
        if mid == 0: # Should not happen as low starts at 1 and A_i >= 1 (so high >= 1)
            low = 1 
            continue
        if can(mid):
            ans = mid
            low = mid + 1 # Try for a larger M
        else:
            high = mid - 1 # M is too large
            
    sys.stdout.write(str(ans) + "\n")

solve()
0