tap the thao

Code

#include <bits/stdc++.h>
#define pb   push_back
#define ll   long long
#define int  long long
#define endl "\n"

using namespace std;

const int N   = 1e4+5;
const int MOD = 1e9+7;

int n, m;
int a[N];
int dp[N][501][3];

signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin >> n >> m;
    for (int i=1;i <= n;i++) {
        cin >> a[i];
    }
    memset(dp, -0x3f, sizeof dp);
    for (int i=0;i <= n;i++) {
        dp[i][0][0] = 0;
    }
//    goi dp[i][j][state] la xet den thoi diem thu i va do met moi la j va state
    for (int i= 0;i <= n;i++) {
        // nghi xong chay
        dp[i+1][1][1] = max(dp[i+1][1][1], dp[i][0][0]+a[i+1]);
        for (int j=0;j <= m;j++) {
            // chay xong chay tiep
            if (0 < j && j < m) dp[i+1][j+1][1] = max(dp[i+1][j+1][1], dp[i][j][1]+a[i+1]);
            // chay xong nghi
            int meh = max(j-1, 0*1ll);
            if (j > 0) dp[i+1][meh][0] = max(dp[i+1][meh][0], dp[i][j][1]);
            // nghi xong nghi
            dp[i+1][meh][0] = max(dp[i+1][meh][0], dp[i][j][0]);
        }
    }
    cout << dp[n][0][0];
    return 0;
}
// Nguyen Minh Hieu - 2008 - Gia Lai.
// https://hieuhfgr.pythonanywhere.com/
// .-.. --- ...- . .-.. -.--