/+ 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; 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); int l = 0, r = 0; foreach (i; n..2*n+1) { //[i-n, i-k] while (r <= i-k) { tr.insert(sm[r]); r++; } while (l < i-n) { tr.removeKey(sm[l]); l++; } if (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/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/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/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) */