Submission #2200927

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main(){
    int N, M, K;
    cin >> N >> M >> K;
    long nums[N];
    for(int i = 0; i < N; i++){
        cin >> nums[i];
    }
    long choose[N][K];
    for(int i = 0; i <= N; i++){
        choose[i][K - 1] = 0;
    }
    for(int i = N - 1; i >= 0; i--){
        for(int j = K - 2; j >= 0; j--){
            long ans = -2e14;
            for(int k = i + 1; k <= i + M && k < N; k++){
                ans = max(ans, nums[k] * long(j + 2) + choose[k][j + 1]);
            }
            choose[i][j] = ans;
        }
    }
    long ans = 0;
    for(int i = 0; i < N; i++){
        ans = max(ans, nums[i] + choose[i][0]);
    }
    cout << ans << endl;
}

Submission Info

Judge Result