#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define REP(i,n) for(int (i)=0; (i)<(n) ;++(i)) #define REPN(i,a,n) FOR((i),(a),(a)+(n)) #define FOR(i,a,b) for(int (i)=(a); (i)<(b) ;++(i)) #define PB push_back #define MP make_pair #define SE second #define FI first #define DBG(a) cerr<<(a)< PLL; typedef vector VLL; typedef pairPI; typedef vector VI; const LL LINF=334ll<<53; const int INF=15<<26; const LL MOD=1E9+7; const double eps=1e-12; typedef vector> Matrix; void multiply(const Matrix &a, const Matrix &b, Matrix &ret){ //ret=a*b int k=a.size(),l=a[0].size(),m=b[0].size(); if(l!=b.size()) DBG("!size") for(int h=0;h> n >> m; if(n==2){cout<< 0 <(1)); vector dp(n),lc(n),dp2(n,1e18); FOR(i,0,n-2) { cin >>c[i+(n-2)][0]; lc[i+1]=c[i+(n-2)][0]; } Matrix a((n-2)*2,vector((n-2)*2));//p[1]~p[m-2]c[1]~c[n-2] Matrix b((n-2)*2,vector((n-2)*2));//p[1]~p[m-2]c[1]~c[n-2] REP(i,n-2){ REP(j,n-2){ if(i=(n-2)*2-m){ a[i][j]+=1.0; a[i][j+(n-2)]+=1.0; } if(i==j){ a[i+(n-2)][j+(n-2)]+=1.0; } a[i][j]/=m; a[i][j+(n-2)]/=m; } } REP(i,20){ multiply(a,a,b); swap(a,b); } Matrix p(2*(n-2),vector(1)); multiply(a,c,p); //REP(i,n-2) cout << i <<' '<< p[i][0]<=0;--i){ FOR(j,i+1,i+m+1){ dp[i]+=dp[j]+lc[j]; dp2[i]=min(dp2[i],p[j-1][0]+lc[j]); } dp[i]=min(dp[i]/m,dp2[i]); } //REP(i,n-2) cout << i <<' '<< dp[i]<