結果
問題 |
No.576 E869120 and Rings
|
ユーザー |
![]() |
提出日時 | 2025-04-20 17:31:02 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 935 bytes |
コンパイル時間 | 3,663 ms |
コンパイル使用メモリ | 279,212 KB |
実行使用メモリ | 8,412 KB |
最終ジャッジ日時 | 2025-04-20 17:31:11 |
合計ジャッジ時間 | 8,371 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 5 RE * 22 |
ソースコード
#include<bits/stdc++.h> using namespace std; int n,k; string s; double pre[500005]; deque<int> q; bool check(double mid) { for(int j=0;j<=2*n;j++) pre[j]=0.0; for(int j=0;j<2*n;j++) { int val=(s[j]=='1')?1:0; pre[j+1]=pre[j]+(val-mid); } q.clear(); for(int j=0;j<2*n;j++) { int now=j+1,ima=now-k; if(ima>=0) { while(!q.empty() && pre[q.back()]>=pre[ima]) q.pop_back(); q.push_back(ima); } int imi=now-n; if(imi<0) imi=0; while(!q.empty() && q.front()<imi) q.pop_front(); if(now>=k) if(!q.empty()) if(pre[now]-pre[q.front()]>=-1e-9) return 1; } return 0; } int main() { cin>>n>>k>>s; s+=s; double l=0.0,r=1.0; for(int _=1;_<=100;_++) { double mid=(l+r)/2; if(check(mid)) l=mid; else r=mid; } printf("%.15f",r); return 0; }