P1353

#include<bits/stdc++.h>
using namespace std;
int d[10005],dp[10005][505][2],n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>d[i];
    for(int j=1;j<=m;j++){
        for(int k=0;k<=1;k++){
            if(!k)dp[1][j][k]=0;
            else dp[1][j][k]=d[1];
        }
    }
    for(int i=2;i<=n;i++){
        dp[i][0][0]=max(dp[i-1][1][0],dp[i-1][1][1]);
        for(int j=1;j<=m;j++){
            if(j+1>m){dp[i][j][0]=max(dp[i-1][j-1][0],dp[i-1][j-1][1]),dp[i][j][1]=0;continue;}
            dp[i][j][0]=max(dp[i-1][j-1][0],dp[i-1][j-1][1]);
            dp[i][j][1]=max(dp[i-1][j+1][0]+d[i],dp[i-1][j+1][1]+d[i]);
        }
    }
    cout<<max(dp[n][0][0],dp[n][0][1]);
}

thx