結果

問題 No.576 E869120 and Rings
ユーザー gew1fw
提出日時 2025-06-12 21:03:31
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,353 bytes
コンパイル時間 199 ms
コンパイル使用メモリ 81,624 KB
実行使用メモリ 124,864 KB
最終ジャッジ日時 2025-06-12 21:05:09
合計ジャッジ時間 5,772 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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()))
    doubled = a + a
    prefix = [0] * (2 * N + 1)
    for i in range(2 * N):
        prefix[i + 1] = prefix[i] + doubled[i]
    
    low = 0.0
    high = 1.0
    for _ in range(100):
        mid = (low + high) / 2
        if check(mid, N, K, prefix):
            low = mid
        else:
            high = mid
    print("{0:.15f}".format(low))

def check(r, N, K, prefix):
    q = deque()
    for i in range(2 * N + 1):
        # Remove elements from the front that are out of the window's start (i - N)
        while q and q[0] < (i - N):
            q.popleft()
        
        # Add j = i - K if applicable
        if i >= K:
            j = i - K
            if j >= 0:
                val_j = prefix[j] - r * j
                # Maintain deque in increasing order of val_j
                while q and (prefix[q[-1]] - r * q[-1]) >= val_j:
                    q.pop()
                q.append(j)
        
        # Check current value against the minimum in the deque
        current_val = prefix[i] - r * i
        if q:
            min_val = prefix[q[0]] - r * q[0]
            if current_val >= min_val:
                return True
    return False

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