結果

問題 No.576 E869120 and Rings
コンテスト
ユーザー lam6er
提出日時 2025-04-16 16:25:56
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,710 bytes
コンパイル時間 607 ms
コンパイル使用メモリ 81,880 KB
実行使用メモリ 112,988 KB
最終ジャッジ日時 2025-04-16 16:27:48
合計ジャッジ時間 5,820 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 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]
    a += a  # Double the array to handle circularity

    # Precompute prefix sums of the doubled array
    pre_sum = [0] * (2 * N + 1)
    for i in range(1, 2 * N + 1):
        pre_sum[i] = pre_sum[i-1] + a[i-1]

    low = 0.0
    high = 1.0
    eps = 1e-12
    iterations = 100  # Sufficient for precision up to 1e-30

    for _ in range(iterations):
        mid = (low + high) / 2
        max_sum = -float('inf')
        dq = deque()

        for j in range(1, 2 * N + 1):
            a_j = max(0, j - N)
            b_j = j - K
            if b_j < a_j:
                continue

            # Remove indices from the front that are out of the current window [a_j, b_j]
            while dq and dq[0] < a_j:
                dq.popleft()

            # Process the current i = b_j
            S_i = pre_sum[b_j] - mid * b_j
            # Remove elements from the back that have S[i] >= current S_i
            while dq:
                last_i = dq[-1]
                S_last = pre_sum[last_i] - mid * last_i
                if S_last >= S_i:
                    dq.pop()
                else:
                    break
            dq.append(b_j)

            # Calculate current_sum for this j
            S_j = pre_sum[j] - mid * j
            current_sum = S_j - (pre_sum[dq[0]] - mid * dq[0])
            if current_sum > max_sum:
                max_sum = current_sum

        if max_sum >= 0:
            low = mid
        else:
            high = mid

    print("{0:.15f}".format(low))

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