/+ dub.sdl: name "A" dependency "dcomp" version=">=0.7.3" +/ import std.stdio, std.algorithm, std.range, std.conv; // import dcomp.foundation, dcomp.scanner; // import dcomp.algorithm; // import dcomp.container.deque; int main() { Scanner sc = new Scanner(stdin); int n, k; sc.read(n, k); string s; sc.read(s); s ~= s; bool pred(double md) { double[] sm = new double[2*n+1]; sm[] = 0; foreach (i; 0..2*n) { sm[i+1] = sm[i] + s[i] - '0' - md; } import std.container.rbtree; // auto tr = redBlackTree!(true, double); auto tr = Deque!int(); int l = 0, r = 0; foreach (i; n..2*n+1) { //[i-n, i-k] while (r <= i-k) { while (tr.length && sm[tr.back] >= sm[r]) tr.removeBack; tr.insertBack(r); // tr.insert(sm[r]); r++; } while (l < i-n) { if (tr.length && tr.front == i) tr.removeFront; // tr.removeKey(sm[l]); l++; } if (sm[tr.front] <= sm[i]) return false; } return true; } writefln("%.20f", binSearch!(md => pred(md))(0.0, 1.0, 50)); return 0; } /* IMPORT /home/yosupo/Program/dcomp/source/dcomp/foundation.d */ // module dcomp.foundation; static if (__VERSION__ <= 2070) { /* Copied by https://github.com/dlang/phobos/blob/master/std/algorithm/iteration.d Copyright: Andrei Alexandrescu 2008-. License: $(HTTP boost.org/LICENSE_1_0.txt, Boost License 1.0). */ template fold(fun...) if (fun.length >= 1) { auto fold(R, S...)(R r, S seed) { import std.algorithm : reduce; static if (S.length < 2) { return reduce!fun(seed, r); } else { import std.typecons : tuple; return reduce!fun(tuple(seed), r); } } } } version (X86) static if (__VERSION__ < 2071) { import core.bitop : bsf, bsr, popcnt; int bsf(ulong v) { foreach (i; 0..64) { if (v & (1UL << i)) return i; } return -1; } int bsr(ulong v) { foreach_reverse (i; 0..64) { if (v & (1UL << i)) return i; } return -1; } int popcnt(ulong v) { int c = 0; foreach (i; 0..64) { if (v & (1UL << i)) c++; } return c; } } /* IMPORT /home/yosupo/Program/dcomp/source/dcomp/container/deque.d */ // module dcomp.container.deque; struct DequePayload(T) { import core.exception : RangeError; import core.memory : GC; import std.range : ElementType, isInputRange; import std.traits : isImplicitlyConvertible; T *d; size_t st, length, cap; @property bool empty() const { return length == 0; } alias opDollar = length; ref inout(T) opIndex(size_t i) inout { version(assert) if (length <= i) throw new RangeError(); return d[(st+i >= cap) ? (st+i-cap) : st+i]; } private void expand() { import std.algorithm : max; assert(length == cap); auto nc = max(size_t(4), 2*cap); T* nd = cast(T*)GC.malloc(nc * T.sizeof); foreach (i; 0..length) { nd[i] = this[i]; } d = nd; st = 0; cap = nc; } void clear() { st = length = 0; } void insertFront(T v) { if (length == cap) expand(); if (st == 0) st += cap; st--; length++; this[0] = v; } void insertBack(T v) { if (length == cap) expand(); length++; this[length-1] = v; } void removeFront() { assert(!empty, "Deque.removeFront: Deque is empty"); st++; length--; if (st == cap) st = 0; } void removeBack() { assert(!empty, "Deque.removeBack: Deque is empty"); length--; } ref inout(T) front() inout { return this[0]; } ref inout(T) back() inout { return this[$-1]; } Range opSlice() {return Range(&this, 0, length); } alias Range = RangeT!(DequePayload!T); alias ConstRange = RangeT!(const DequePayload!T); alias ImmutableRange = RangeT!(immutable DequePayload!T); static struct RangeT(A) { import std.traits : CopyTypeQualifiers; alias E = CopyTypeQualifiers!(A, T); A *p; size_t a, b; @property bool empty() const { return b <= a; } @property size_t length() const { return b-a; } @property RangeT save() { return RangeT(p, a, b); } @property RangeT!(const A) save() const { return typeof(return)(p, a, b); } alias opDollar = length; @property ref inout(E) front() inout { return (*p)[a]; } @property ref inout(E) back() inout { return (*p)[b-1]; } void popFront() { version(assert) if (empty) throw new RangeError(); a++; } void popBack() { version(assert) if (empty) throw new RangeError(); b--; } ref inout(E) opIndex(size_t i) inout { return (*p)[i]; } RangeT opSlice() { return this.save; } RangeT opSlice(size_t i, size_t j) { version(assert) if (i > j || a + j > b) throw new RangeError(); return typeof(return)(p, a+i, a+j); } RangeT!(const A) opSlice() const { return this.save; } RangeT!(const A) opSlice(size_t i, size_t j) const { version(assert) if (i > j || a + j > b) throw new RangeError(); return typeof(return)(p, a+i, a+j); } } } struct Deque(T, bool mayNull = true) { import core.exception : RangeError; import core.memory : GC; import std.range : ElementType, isInputRange; import std.traits : isImplicitlyConvertible; alias Payload = DequePayload!T; alias Range = Payload.Range; alias ConstRange = Payload.ConstRange; alias ImmutableRange = Payload.ImmutableRange; Payload* p; private void I() { if (mayNull && !p) p = new Payload(); } private void C() const { version(assert) if (mayNull && !p) throw new RangeError(); } static if (!mayNull) { @disable this(); } private this(Payload* p) { this.p = p; } this(U)(U[] values...) if (isImplicitlyConvertible!(U, T)) { p = new Payload(); foreach (v; values) { insertBack(v); } } this(Range)(Range r) if (isInputRange!Range && isImplicitlyConvertible!(ElementType!Range, T) && !is(Range == T[])) { p = new Payload(); foreach (v; r) { insertBack(v); } } static Deque make() { return Deque(new Payload()); } @property bool havePayload() const { return (!mayNull || p); } @property bool empty() const { return (!havePayload || p.empty); } @property size_t length() const { return (havePayload ? p.length : 0); } alias opDollar = length; ref inout(T) opIndex(size_t i) inout {C; return (*p)[i]; } ref inout(T) front() inout {C; return (*p)[0]; } ref inout(T) back() inout {C; return (*p)[$-1]; } void clear() { if (p) p.clear(); } void insertFront(T v) {I; p.insertFront(v); } void insertBack(T v) {I; p.insertBack(v); } alias stableInsertBack = insertBack; void removeFront() {C; p.removeFront(); } void removeBack() {C; p.removeBack(); } Range opSlice() {I; return Range(p, 0, length); } } /* IMPORT /home/yosupo/Program/dcomp/source/dcomp/algorithm.d */ // module dcomp.algorithm; import std.range.primitives; import std.traits : isFloatingPoint, isIntegral; T binSearch(alias pred, T)(T l, T r) if (isIntegral!T) { while (r-l > 1) { T md = (l+r)/2; if (!pred(md)) l = md; else r = md; } return r; } T binSearch(alias pred, T)(T l, T r, int cnt = 60) if (isFloatingPoint!T) { foreach (i; 0..cnt) { T md = (l+r)/2; if (!pred(md)) l = md; else r = md; } return r; } E minimum(alias pred = "a < b", Range, E = ElementType!Range)(Range range, E seed) if (isInputRange!Range && !isInfinite!Range) { import std.algorithm, std.functional; return reduce!((a, b) => binaryFun!pred(a, b) ? a : b)(seed, range); } ElementType!Range minimum(alias pred = "a < b", Range)(Range range) { assert(!range.empty, "range must not empty"); auto e = range.front; range.popFront; return minimum!pred(range, e); } E maximum(alias pred = "a < b", Range, E = ElementType!Range)(Range range, E seed) if (isInputRange!Range && !isInfinite!Range) { import std.algorithm, std.functional; return reduce!((a, b) => binaryFun!pred(a, b) ? b : a)(seed, range); } ElementType!Range maximum(alias pred = "a < b", Range)(Range range) { assert(!range.empty, "range must not empty"); auto e = range.front; range.popFront; return maximum!pred(range, e); } Rotator!Range rotator(Range)(Range r) { return Rotator!Range(r); } struct Rotator(Range) if (isForwardRange!Range && hasLength!Range) { size_t cnt; Range start, now; this(Range r) { cnt = 0; start = r.save; now = r.save; } this(this) { start = start.save; now = now.save; } @property bool empty() { return now.empty; } @property auto front() { assert(!now.empty); import std.range : take, chain; return chain(now, start.take(cnt)); } @property Rotator!Range save() { return this; } void popFront() { cnt++; now.popFront; } } /* IMPORT /home/yosupo/Program/dcomp/source/dcomp/scanner.d */ // module dcomp.scanner; // import dcomp.array; class Scanner { import std.stdio : File; import std.conv : to; import std.range : front, popFront, array, ElementType; import std.array : split; import std.traits : isSomeChar, isStaticArray, isArray; import std.algorithm : map; File f; this(File f) { this.f = f; } char[512] lineBuf; char[] line; private bool succW() { import std.range.primitives : empty, front, popFront; import std.ascii : isWhite; while (!line.empty && line.front.isWhite) { line.popFront; } return !line.empty; } private bool succ() { import std.range.primitives : empty, front, popFront; import std.ascii : isWhite; while (true) { while (!line.empty && line.front.isWhite) { line.popFront; } if (!line.empty) break; line = lineBuf[]; f.readln(line); if (!line.length) return false; } return true; } private bool readSingle(T)(ref T x) { import std.algorithm : findSplitBefore; import std.string : strip; import std.conv : parse; if (!succ()) return false; static if (isArray!T) { alias E = ElementType!T; static if (isSomeChar!E) { auto r = line.findSplitBefore(" "); x = r[0].strip.dup; line = r[1]; } else static if (isStaticArray!T) { foreach (i; 0..T.length) { bool f = succW(); assert(f); x[i] = line.parse!E; } } else { FastAppender!(E[]) buf; while (succW()) { buf ~= line.parse!E; } x = buf.data; } } else { x = line.parse!T; } return true; } int read(T, Args...)(ref T x, auto ref Args args) { if (!readSingle(x)) return 0; static if (args.length == 0) { return 1; } else { return 1 + read(args); } } } /* IMPORT /home/yosupo/Program/dcomp/source/dcomp/array.d */ // module dcomp.array; T[N] fixed(T, size_t N)(T[N] a) {return a;} struct FastAppender(A, size_t MIN = 4) { import std.algorithm : max; import std.conv; import std.range.primitives : ElementEncodingType; import core.stdc.string : memcpy; private alias T = ElementEncodingType!A; private T* _data; private uint len, cap; @property size_t length() const {return len;} bool empty() const { return len == 0; } void reserve(size_t nlen) { import core.memory : GC; if (nlen <= cap) return; void* nx = GC.malloc(nlen * T.sizeof); cap = nlen.to!uint; if (len) memcpy(nx, _data, len * T.sizeof); _data = cast(T*)(nx); } void free() { import core.memory : GC; GC.free(_data); } void opOpAssign(string op : "~")(T item) { if (len == cap) { reserve(max(MIN, cap*2)); } _data[len++] = item; } void insertBack(T item) { this ~= item; } void removeBack() { len--; } void clear() { len = 0; } ref inout(T) back() inout { assert(len); return _data[len-1]; } ref inout(T) opIndex(size_t i) inout { return _data[i]; } T[] data() { return (_data) ? _data[0..len] : null; } } /* This source code generated by dcomp and include dcomp's source code. dcomp's Copyright: Copyright (c) 2016- Kohei Morita. (https://github.com/yosupo06/dcomp) dcomp's License: MIT License(https://github.com/yosupo06/dcomp/blob/master/LICENSE.txt) */