結果

問題 No.576 E869120 and Rings
コンテスト
ユーザー lam6er
提出日時 2025-04-15 23:39:43
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,662 bytes
コンパイル時間 140 ms
コンパイル使用メモリ 82,704 KB
実行使用メモリ 277,252 KB
最終ジャッジ日時 2025-04-15 23:41:19
合計ジャッジ時間 5,948 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other MLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    N, K = map(int, sys.stdin.readline().split())
    a_str = sys.stdin.readline().strip()
    a = [int(c) for c in a_str]
    duplicated = a + a  # Handle circularity by duplicating the array

    low = 0.0
    high = 1.0
    # Perform binary search with sufficient iterations for precision
    for _ in range(100):
        mid = (low + high) / 2
        if is_possible(duplicated, N, K, mid):
            low = mid
        else:
            high = mid
    # Output with enough decimal places
    print("{0:.15f}".format(low))

def is_possible(arr, N, K, x):
    n = len(arr)
    prefix = [0.0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + (arr[i] - x)
    dq = deque()
    found = False
    for i in range(1, n + 1):
        if i < K:
            continue  # Subarray length would be less than K
        j_end = i - K
        j_start = max(0, i - N)
        if j_start > j_end:
            continue  # No valid j in this range

        # Maintain deque with indices in [j_start, j_end] having minimal prefix[j]
        # Add j_end to the deque, removing larger elements from the end
        while dq and prefix[j_end] <= prefix[dq[-1]]:
            dq.pop()
        dq.append(j_end)
        # Remove elements from the front that are out of the current window
        while dq and dq[0] < j_start:
            dq.popleft()
        # Check if current window has a valid sum
        if dq:
            if prefix[i] - prefix[dq[0]] >= -1e-9:  # Account for floating point precision
                found = True
                break
    return found

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