#[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![0.].into_iter() .chain( a.iter().cloned() .chain(a.iter().cloned()) .map(|e| e as f64 - x) ).collect(); debug!(a); for i in 0..a.len() - 1 { a[i + 1] += a[i]; } debug!(a); let a = a.into_iter().map(|x| Reverse(Ordered(x))).collect(); let maxi: Vec<_> = sliding_minimum( &a, n - k, ).into_iter().map(|Reverse(Ordered(x))| x).collect(); let a: Vec<_> = a.into_iter().map(|Reverse(Ordered(x))| x).collect(); debug!(maxi); for (&l, &rmax) in a.iter().take(n+1).zip(maxi.iter().cycle().skip(k)) { if l < rmax { return false; } } true }; debug!(check(1.)); let mut l = 0.; let mut r = 1.; for _ in 0..20 { let m = (l + r) / 2.; let res = check(m); // debug!(res); if res { r = m; } else { l = m; } } printfln!("{}", r); }