# Untitled

unknown
plain_text
19 days ago
1.3 kB
2
Indexable
Never
#include <bits/stdc++.h>
using namespace std;

int main()
{
// input output
int n, k;
cin >> n >> k;
vector<int> A(n);
for (int i = 0; i < n; i++) {
cin >> A[i];
}

vector<vector<int>> dp(n, vector<int>(k+1, 0));
for (int i = n - 1; i >= 0; i--) {
for (int j = k; j >= 0; j--) {
int skip = A[i] + (i+1 < n && j+1 <= k ? dp[i+1][j+1] : 0);
int next = i+1 < n ? dp[i+1][0] : 0;
dp[i][j] = max(skip, next);
}
}

cout << dp[0][0] << endl;

return 0;
}

/*
// #1: Recursion + memo
#include <bits/stdc++.h>
using namespace std;

int n, k;
vector<int> A;
map<pair<int, int>, int> memo;

int solve(int i, int consecutive) {
if (i >= n) return 0;

pair<int, int> key = make_pair(i, consecutive);
if (memo.count(key)) {
return memo[key];
}

int next = 0, skip = 0;
if (consecutive <= k) {
next = A[i] + solve(i + 1, consecutive + 1);
}

skip = solve(i + 1, 0);

int ans = max(next, skip);
memo[key] = ans;
return ans;
}

int main()
{
// input output
cin >> n >> k;

A.resize(n);
for (int i = 0; i < n; i++) {
cin >> A[i];
}

int ans = solve(0, 0);
cout << ans;
return 0;
}
*/