結果

問題 No.576 E869120 and Rings
ユーザー gew1fw
提出日時 2025-06-12 21:06:16
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,352 bytes
コンパイル時間 536 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 121,884 KB
最終ジャッジ日時 2025-06-12 21:08:27
合計ジャッジ時間 6,277 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 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()))
    arr = a + a  # Double the array to handle circularity
    prefix = [0] * (len(arr) + 1)
    for i in range(len(arr)):
        prefix[i+1] = prefix[i] + arr[i]
    
    low = 0.0
    high = 1.0
    eps = 1e-12
    for _ in range(100):
        mid = (low + high) / 2
        if check(prefix, N, K, mid):
            low = mid
        else:
            high = mid
    print("{0:.15f}".format(low))

def check(prefix, N, K, x):
    deque_ = deque()
    max_j = 2 * N  # Since the array is doubled
    for j in range(2 * N + 1):
        current_val = prefix[j] - x * j
        if j >= K:
            i_candidate = j - K
            if i_candidate >= 0:
                val = prefix[i_candidate] - x * i_candidate
                while deque_ and (prefix[deque_[-1]] - x * deque_[-1]) >= val:
                    deque_.pop()
                deque_.append(i_candidate)
            i_min = max(0, j - N)
            while deque_ and deque_[0] < i_min:
                deque_.popleft()
            if deque_:
                min_val = prefix[deque_[0]] - x * deque_[0]
                if current_val >= min_val:
                    return True
    return False

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