部隊中共有N個士兵，每個士兵有各自的能力指數Xi，在一次演練中，指揮部確定了M個需要防守的地點，按重要程度從低到高排序，依次以數字1到M標注每個地點的重要程度，指揮部將選擇M個士兵依次進入指定地點進行防守任務，能力指數為X的士兵防守重要程度為Y的地點將得到X*Y的參考指數。現在士兵們排成一排，請你選擇出連續的M個士兵依次參加防守,使得總的參考指數值最大。

輸入包含多組數據。

輸入第一行有兩個整數N,M(1<=N<=1000000，1<=M<=1000),第二行N個整數表示每個士兵對應的能力指數Xi（1<=Xi<=1000）。

對于30%的數據1<=M<=N<=1000。

輸出一個整數，為最大的參考指數總和。

5 32 1 3 1 4Sample Output
17注意讀題，是連續的士兵。找到規律，模擬士兵的選取過程，遍歷所有士兵，過程維護中最大值，時間復雜度為o（n）。規律：以樣例數據為例，第一組數據，2*1+1*2+3*3，第二組數據，1*1+3*2+1*3。可以看出第二組就是第一組減去，2 1 3三個數的和再加上第四個數乘以m。比較抽象，建議手動模擬幾組數據，這樣比較容易理解。模擬就是按照規律模擬的。詳細見代碼。AC代碼：
#include <iostream>#include <math.h>#include <algorithm>#include <string.h>#include <stdio.h>using namespace std;long long n,m,hum[1000005],sum,peo,i,tmax;int main(){    while(~scanf("%lld%lld",&n,&m))    {        for(i=1; i<=n; i++)        {            scanf("%lld",&hum[i]);        }        sum=0;peo=0;        for(i=1;i<=m;i++)        {            sum+=hum[i]*i;            peo+=hum[i];每次減去的m個人的能力指數的和        }        tmax=sum;        for(i=m+1;i<=n;i++)        {            sum=sum-peo+hum[i]*m;模擬的過程            peo=peo-hum[i-m]+hum[i];維護m個人的能力指數的和            tmax=max(sum,tmax);        }        PRintf("%lld/n",tmax);    }    return 0;}