結果

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

ソースコード

diff # 

import sys
from collections import deque

def main():
    N, K = map(int, sys.stdin.readline().split())
    s = sys.stdin.readline().strip()
    A = [int(c) for c in s]
    duplicated = A + A

    low = 0.0
    high = 1.0
    eps = 1e-10
    for _ in range(100):
        mid = (low + high) / 2
        if check(duplicated, N, K, mid, eps):
            low = mid
        else:
            high = mid
    print("{0:.15f}".format(low))

def check(duplicated, N, K, x, eps):
    n = len(duplicated)
    prefix = [0.0] * (n + 1)
    for i in range(1, n+1):
        prefix[i] = prefix[i-1] + (duplicated[i-1] - x)
    dq = deque()
    found = False
    for i in range(1, n+1):
        if i < K:
            continue
        window_start = max(0, i - N)
        window_end = i - K
        if window_end < 0:
            continue
        j = window_end
        # Add j to deque maintaining increasing order of prefix[j]
        while dq and prefix[j] <= prefix[dq[-1]]:
            dq.pop()
        dq.append(j)
        # Remove elements from the front that are out of the window
        while dq and dq[0] < window_start:
            dq.popleft()
        # Check if current sum is non-negative
        if dq:
            current = prefix[i] - prefix[dq[0]]
            if current >= -eps:
                found = True
                break
    return found

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