#include // c #include // io #include #include #include #include // container #include #include #include #include #include #include // other #include #include #include #include #include using namespace std; typedef long long ll;typedef unsigned long long ull;typedef long double ld; #define ALL(c) c.begin(),c.end() #define IN(l,v,r) (l<=v && v < r) template void UNIQUE(T& v){v.erase(unique(ALL(v)),v.end());} //debug #define DUMP(x) cerr << #x <<" = " << (x) #define LINE() cerr<< " (L" << __LINE__ << ")" struct range{ struct Iter{ int v,step; Iter& operator++(){v+=step;return *this;} bool operator!=(Iter& itr){return vitr.v;} int& operator*(){return v;} }; Iter i, n; rrange(int i, int n,int step):i({i-1,step}), n({n-1,step}){} rrange(int i, int n):rrange(i,n,1){} rrange(int n) :rrange(0,n){} Iter& begin(){return n;} Iter& end(){return i;} }; //input template istream& operator >> (istream& is,pair& p){return is>>p.first>>p.second;} template istream& operator >> (istream& is,tuple& t){return is >> get<0>(t);} template istream& operator >> (istream& is,tuple& t){return is >> get<0>(t) >> get<1>(t);} template istream& operator >> (istream& is,tuple& t){return is >>get<0>(t)>>get<1>(t)>>get<2>(t);} template istream& operator >> (istream& is,tuple& t){return is >> get<0>(t)>>get<1>(t)>>get<2>(t)>>get<3>(t);} template istream& operator >> (istream& is,vector& as){for(int i:range(as.size()))is >>as[i];return is;} //output template ostream& operator << (ostream& os, const set& ss){for(auto a:ss){if(a!=ss.begin())os<<" "; os< ostream& operator << (ostream& os, const pair& p){return os< ostream& operator << (ostream& os, const map& m){bool isF=true;for(auto& p:m){if(!isF)os< ostream& operator << (ostream& os, const tuple& t){return os << get<0>(t);} template ostream& operator << (ostream& os, const tuple& t){return os << get<0>(t)<<" "<(t);} template ostream& operator << (ostream& os, const tuple& t){return os << get<0>(t)<<" "<(t)<<" "<(t);} template ostream& operator << (ostream& os, const tuple& t){return os << get<0>(t)<<" "<(t)<<" "<(t)<<" "<(t);} template ostream& operator << (ostream& os, const vector& as){for(int i:range(as.size())){if(i!=0)os<<" "; os< ostream& operator << (ostream& os, const vector>& as){for(int i:range(as.size())){if(i!=0)os< inline T INF(){assert(false);}; template<> inline int INF(){return 1<<28;}; template<> inline ll INF(){return 1LL<<60;}; template<> inline double INF(){return 1e16;}; template<> inline long double INF(){return 1e16;}; template inline T EPS(){assert(false);}; template<> inline int EPS(){return 1;}; template<> inline ll EPS(){return 1LL;}; template<> inline double EPS(){return 1e-12;}; template<> inline long double EPS(){return 1e-12;}; // min{2^r | n < 2^r} template inline T upper_pow2(T n){ T res=1;while(res inline T msb(T n){ int d=62;while((1LL<n)d--;return d;} template T pmod(T v,U M){return (v%M+M)%M;} namespace Matrix{ class Inconsistent{};//none class Ambiguous{};//many class NoSolution{}; template class Mat :public vector>{ public: const int H,W; Mat(int H,int W):vector>(H,vector(W)),H(H),W(W){ for(int y:range(H))for(int x:range(W)) (*this)[y][x] = ve; } const T ve = 0.0; inline T vc(T a,T b){return a+b;} inline T vinv(T a){return -a;} const T vme = 1.0; inline T vmc(T a,T b){return a*b;} inline T vminv(T a){return 1/a;} inline T sig(T a,T b = 0){return a-b>EPS()?+1:a-b<-EPS()?-1:0;} const inline Mat e(){ return vector>(H,vector(W,ve)); } inline Mat c(Mat a,Mat b){return a+b;} inline Mat inv(Mat a){return -a;} const inline Mat me(){ static Mat A(H,W); for(int y:range(H))for(int x:range(W))A[y][x]= ve; for(int i:range(min(H,W)))A[i][i]= vme; return A; } inline Mat mc(Mat a,Mat b){return a*b;} //O(n^2) Mat operator+(const Mat& r){ const Mat& l=*this; Mat res(l.H,r.W); for(int y:range(l.H))for(int x:range(r.W)) res[y][x]= c(l[y][x],r[y][x]); return res; } //O(n^2) Mat operator-(){ Mat res=*this; for(int y:range(res.H))for(int x:range(res.W)) res[y][x] = inv(res[y][x]); return res; } Mat operator-(const Mat& r){ return (*this) + (-r); } //O(n^3) Mat operator*(const Mat& r){ const Mat& l=*this; Mat res(l.H,r.W); for(int y:range(l.H))for(int x:range(r.W))for(int k:range(r.H)) res[y][x] = c(res[y][x], mc(l[y][k],r[k][x])); return res; } //O(n^2) vector operator*(const vector& r){ const Mat& l=*this; vector res(r.size()); for(int y:range(l.H))for(int x:range(l.W)) res[y] = c(res[y],mc(l[y][x],r[x])); return res; } // O(n^3*log(d)) // Mat x must be n*n size //:TODO abstraction Mat pow(ll d){ Mat x=*this,res=e(); while(d!=0){ if(d%2)res=res*x; x=x*x; d/=2; } return res; } //O(n^3) //Ax = b void gauss(vector& b){ Mat A=*this; int py =0,px = 0; while(py < H && px < W){ for(int y=py+1;y 0){ swap(A[y],A[py]);swap(b[y],b[py]); } } if(sig(A[py][px]) != 0){ T d = vminv(A[py][px]); for(int x=0;x=0;x--)for(int y=0;y> n >> m; vector cs(n); for(int i:range(1,n-1)){ ld v;cin >> v;cs[i] = v; } Mat mat(n,n); vector bs(n); for(int s:range(n-m-1)) mat[s][s] = 1; for(int s:range(n-m-1,n)){ bs[s] = m*cs[s]; mat[s][s] = m; if(s < n-1){ for(int e:range(1,m+1)){ if(s+e < n){ mat[s][(s+e)] -= 1.0; }else{ mat[s][n-1 - (s+e - (n-1))] -= 1.0; } } } } mat.gauss(bs); vector> dp(n,vector(2,INF())); for(int i:rrange(n-m-1,n)){ dp[i][0] = bs[i] - cs[i]; dp[i][1] = 0; } for(int i:rrange(0,n-m-1)){ for(int x:range(2)){ ld sum = 0; for(int d:range(1,m+1)) sum += (cs[i+d]+dp[i+d][x])/m; dp[i][x] = min(dp[i][x],sum); } for(int d:range(1,m+1)) dp[i][1] = min(dp[i][1],cs[i+d]+dp[i+d][0]); } // cerr << dp << endl; cout << dp[0][1] << endl; } }; int main(){ cout <