B - The staircase

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1e3 + 5;
const int mod = 1e9 + 7;
const int INF = 1e18;
int a[N];
int dp[N];

signed main()
{
    int n , k;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    cin >> k;
    for(int i = 1; i <= (n + 1); i++){
        int m = INT_MIN;
        for(int j = (i - 1); j >= max(i - k , 0ll); j--){
            m = max(m , dp[j]);
        }
        dp[i] = m + a[i];
    }
    cout << dp[n + 1] << endl;
}