Luxurious Hotel)

#include<stdio.h>
int qs[100010];
int n,k,p;

int max(int a,int b){
    return (a > b ? a : b);
}

int cal(int R,int F)
{
    if(R <= 0 || F == 0){
        return 0;
    }
    int nc = cal(R-1,F);
    int c;
    if(R-p-1 >= 0){
        c = cal(R-p,F-1) + qs[R] - qs[R-p];
    }else{
        c = qs[R];
    }
    int ans = max(nc,c);
    return ans;
}

int main()
{
    scanf("%d %d %d",&n,&k,&p);
    for(int i = 1 ; i <= n ; i ++){
        scanf("%d",&qs[i]);
        qs[i] = qs[i] + qs[i-1];
    }
//  printf("%d\n",cal(n,k));
    int dp[n+1][2];
    for(int i = 0 ; i <= n ; i ++){
        for(int j = 0 ; j <= 1 ; j ++){
            dp[i][j] = 0;
        }
    }
    for(int F = 1 ; F <= k ; F++){
        for(int R = 1 ; R <= n; R ++){
            int nc = dp[R-1][F%2];
            int c;
            if(R-p-1 >= 0){
                if(F == 1){
                    c = qs[R] - qs[R-p];
                }
                else{
                    c = dp[R-p][(F+1)%2] + qs[R] - qs[R-p];
                }
            }else{
                c = qs[R];
            }
            dp[R][F%2] = max(c,nc);
    //      printf("%d ",dp[R][F%2]);
        }
    //  printf("\n");
    }
//  printf("\n");
    printf("%d",dp[n][k%2]);
    return 0;
}