CUBE-180: Destruction

#include <bits/stdc++.h>

using namespace std;
using lli = long long;
const int N = 5e4;
const lli INF = 2e18;
int n, k, m;
lli qs[N+10];
lli mn[N+10][2];
lli dp[N+10][2];

int main(){

    scanf("%d%d%d", &n, &k, &m);

    mn[0][0] = INF;
    for(int i=1;i<=n;i++) {
        scanf("%lld", &qs[i]);
        qs[i] += qs[i-1];
        mn[i][0] = min(mn[i-1][0], -qs[i-1]);
    }

    // for(int j=1;j<=k;j++) dp[0][j] = INF; ใส่ใน loop

    // opt mem (3)
    /*
    เนื่องจากพิจารณาเฉพาะ j-1 กับ j เท่านั้น
    loop for j=1 -> k
            for i=1 -> n
                เพื่อให้ opt mem ในการเรียกช่อง array ได้
    */
    dp[0][0] = INF;
    for(int j=1;j<=k;j++){
        dp[0][j%2] = INF;
        mn[0][j%2] = INF;
        for(int i=1;i<=n;i++){
            dp[i][j%2] = dp[i-1][j%2];
            if(i-m+1 >= 1) dp[i][j%2] = min(dp[i][j%2], qs[i] + mn[i-m+1][(j-1)%2]);
            mn[i][j%2] = mn[i-1][j%2];
            if(i>=2) mn[i][j%2] = min(mn[i][j%2], -qs[i-1] + dp[i-2][j%2]);
        }
    }

    printf("%lld", qs[n] - dp[n][k%2]);

    // opt time (2)
    /*
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            dp[i][j] = dp[i-1][j];
            if(i-m+1 >= 1) dp[i][j] = min(dp[i][j], qs[i] + mn[i-m+1][j-1]);
            if(i-2 < 0) mn[i][j] = min(mn[i][j], -qs[i-1]);
            else mn[i][j] = min(mn[i-1][j], -qs[i-1] + dp[i-2][j]);
        }
    }
    */

    // topdown (1)
    /*
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            dp[i][j] = dp[i-1][j];
            for(int idx=1;idx<=i-m+1;idx++){
                if(j == 1)
                    dp[i][j] = min(dp[i][j], qs[i] - qs[idx-1]);
                else if(idx >= 2)
                    dp[i][j] = min(dp[i][j], qs[i] - qs[idx-1] + dp[idx-2][j-1]);
            }
            printf("\n");
        }
    }
    */

    return 0;
}
/***
7 1 3
1 0 4 8 5 7 6
26
12 3 2
2 -8 3 -4 5 -7 3 5 -2 2 4 1
17
*/