結果

問題 No.576 E869120 and Rings
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 21:03:29
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,384 bytes
コンパイル時間 319 ms
コンパイル使用メモリ 82,180 KB
実行使用メモリ 282,024 KB
最終ジャッジ日時 2025-06-12 21:05:02
合計ジャッジ時間 5,901 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other MLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from collections import deque

def main():
    N, K = map(int, sys.stdin.readline().split())
    a = list(map(int, sys.stdin.readline().strip()))
    doubled = a + a
    low = 0.0
    high = 1.0
    eps = 1e-12
    for _ in range(100):
        mid = (low + high) / 2
        if is_possible(doubled, N, K, mid):
            low = mid
        else:
            high = mid
    print("{0:.15f}".format(low))

def is_possible(doubled, N, K, x):
    b = [num - x for num in doubled]
    prefix = [0.0] * (len(b) + 1)
    for i in range(len(b)):
        prefix[i+1] = prefix[i] + b[i]
    dq = deque()
    found = False
    for j in range(1, len(prefix)):
        if j < K:
            continue
        current_i = j - K
        # Add current_i to the deque, maintaining it in increasing order of prefix sum
        while dq and prefix[current_i] <= prefix[dq[-1]]:
            dq.pop()
        dq.append(current_i)
        # Calculate the start of the window
        s = max(0, j - N)
        # Remove elements from the front that are out of the window
        while dq and dq[0] < s:
            dq.popleft()
        if dq:
            # Check if the current window has a valid sum
            if prefix[j] - prefix[dq[0]] >= -1e-9:  # Allowing for small precision errors
                found = True
                break
    return found

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