#[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 } #[allow(unused_imports)] use std::cmp::{max, min}; #[allow(unused_imports)] use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque}; #[allow(unused_imports)] use std::collections::btree_map::Entry::{Occupied, Vacant}; #[derive(PartialEq, PartialOrd, Debug)] struct Ordered(T); impl std::cmp::Eq for Ordered where T: std::cmp::PartialOrd, {} impl std::cmp::Ord for Ordered where T: std::cmp::PartialOrd, { fn cmp(&self, other: &Self) -> std::cmp::Ordering { self.partial_cmp(other).unwrap() } } 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(); let check = |x| { // debug!(x); let mut set = VecDeque::new(); set.push_back(0.); for &e in &a { let b = *set.back().unwrap(); set.push_back(b + e as f64 - x); } // debug!(set); let mut os = BTreeMap::new(); for e in set.iter().skip(k).cloned().map(Ordered) { *os.entry(e).or_insert(0) += 1; } for &e in &a { // debug!(set); // debug!(os); { let (Ordered(min), _) = os.iter().rev().next().unwrap(); let min = *min; // debug!((min, *set.front().unwrap())); if min > *set.front().unwrap() { return false; } } // os.remove(&Ordered(*set.get(k).unwrap())); *os.entry(Ordered(*set.get(k).unwrap())).or_insert(-1) -= 1; if *os.get(&Ordered(*set.get(k).unwrap())).unwrap() == 0 { os.remove(&Ordered(*set.get(k).unwrap())); } // debug!(os); set.pop_front(); let b = *set.back().unwrap(); // os.insert(Ordered(b + e as f64 - x)); *os.entry(Ordered(b + e as f64 - x)).or_insert(0) += 1; // debug!(os); set.push_back(b + e as f64 - x); } true }; // for e in 0..100 { // let mut a = 0.01 * e as f64; // debug!(check(a)); // } // debug!(check(0.9)); let mut l = 0.; let mut r = 1.; for _ in 0..50 { let m = (l+r)/2.; let res = check(m); // debug!(res); if res { r = m; } else { l = m; } } printfln!("{}", r); }