#[allow(dead_code)] fn getline() -> String { let mut res = String::new(); std::io::stdin().read_line(&mut res).ok(); res } #[allow(unused_macros)] macro_rules! readl { ($t: ty) => { { let s = getline(); s.trim().parse::<$t>().unwrap() } }; ($( $t: ty),+ ) => { { let s = getline(); let mut iter = s.trim().split(' '); ($(iter.next().unwrap().parse::<$t>().unwrap(),)*) } }; } #[allow(unused_macros)] macro_rules! readlvec { ($t:ty) => {{ let s = getline(); let iter = s.trim().split(' '); iter.map(|x| x.parse().unwrap()).collect::>() }}; } #[allow(unused_macros)] // macro_rules! debug { // ($x:expr) => { // println!("{}: {:?}", stringify!($x), $x) // }; // } macro_rules! debug { ($x: expr) => () } #[allow(dead_code)] fn show(iter: T) -> String where T: Iterator, T::Item: std::fmt::Display, { let mut res = iter.fold(String::new(), |sum, e| sum + &format!("{} ", e)); res.pop(); res } fn sliding_minimum(a: &Vec, width: usize) -> Vec where T: std::cmp::PartialOrd + Clone { let mut res = Vec::with_capacity(a.len() - width); let mut set = std::collections::VecDeque::new(); for (i, e) in a.iter().enumerate().take(width) { while let Some((v, i)) = set.pop_back() { if v < e { set.push_back((v, i)); break; } } set.push_back((e, i)); } for (s, e) in a.iter().skip(width).enumerate() { res.push(set.front().expect("sliding_minimum error").0.clone()); while let Some((v, i)) = set.pop_back() { if v < e { set.push_back((v, i)); break; } } set.push_back((e, s + width)); while let Some((v, i)) = set.pop_front() { if s + 1 <= i { set.push_front((v, i)); break; } } } res.push(set.front().expect("sliding_minimum error").0.clone()); res } #[allow(unused_imports)] use std::cmp::{max, min}; #[allow(unused_imports)] use std::collections::btree_map::Entry::{Occupied, Vacant}; #[allow(unused_imports)] use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque}; #[derive(PartialEq, PartialOrd, Debug, Clone)] struct Ordered(T); impl Eq for Ordered where T: PartialOrd + Clone, { } impl Ord for Ordered where T: PartialOrd + Clone, { fn cmp(&self, other: &Self) -> std::cmp::Ordering { self.partial_cmp(other).unwrap() } } impl Copy for Ordered {} impl Ordered { fn unwrap(self) -> T { let Ordered(res) = self; res } } #[derive(Eq, PartialEq, Clone, Debug)] struct Reverse(T); impl PartialOrd for Reverse { fn partial_cmp(&self, other: &Reverse) -> Option { other.0.partial_cmp(&self.0) } } impl Ord for Reverse { fn cmp(&self, other: &Reverse) -> std::cmp::Ordering { other.0.cmp(&self.0) } } fn main() { use std::io::Write; let out = std::io::stdout(); let mut out = std::io::BufWriter::new(out.lock()); macro_rules! printf { ($($arg:tt)*) => (write!(out, $($arg)*).unwrap()); } macro_rules! printfln { () => (writeln!(out).unwrap()); ($($arg:tt)*) => (writeln!(out, $($arg)*).unwrap()); } let (n, k) = readl!(usize, usize); let a: Vec = readl!(String) .into_bytes() .into_iter() .map(|x| if x == b'0' { 0 } else { 1 }) .collect(); if n == 1 { printfln!("{}", a[0]); return; } // let check = |x: f64| { // let mut a: Vec<_> = vec![Reverse(Ordered(0.))].into_iter() // .chain( // a.iter().cloned() // .chain(a.iter().cloned()) // .map(|e| Reverse(Ordered(e as f64 - x))) // ).collect(); // for i in 0..a.len() - 1 { // (a[i + 1].0).0 += (a[i].0).0; // } // let maxi: Vec<_> = sliding_minimum( // &a, // n - k, // ).into_iter().map(|Reverse(Ordered(x))| x).collect(); // for (Reverse(Ordered(l)), &rmax) in a.into_iter().take(n+1).zip(maxi.iter().cycle().skip(k)) { // if l < rmax { // return false; // } // } // true // }; // let check = |h| { // let mut min = -1e15; // let mut cur = 0; // let cum = vec![0; n*2+1]; // for (i, j) in // true // }; let a: Vec<_> = a.iter().cloned().chain(a.iter().cloned()).collect(); let check = |x| { let mut r = 0.; let mut l = 0.; let mut minl = 1e99; let mut li = 0; for ri in 0..n*2 { while li + k <= ri { if minl > l { minl = l; } l += a[li] as f64 - x; li += 1; } if r > minl { return false; } r += a[ri] as f64 - x; } true }; let mut l = 0.; let mut r = 1.; for _ in 0..30 { let m = (l + r) / 2.; let res = check(m); // debug!(res); if res { r = m; } else { l = m; } } printfln!("{}", (l+r)/2.); }