Teamwork

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	freopen("teamwork.in", "r", stdin);
	freopen("teamwork.out", "w", stdout);
 
	int n, k;
	cin >> n >> k;
	vector<int> skill(n);
	for (int i = 0; i < n; i++) { cin >> skill[i]; }
 
	vector<int> dp(n, -1);
	for (int i = 0; i < n; i++) {
		// by not joining it to a team, the default value is just skill[i]
		int cur = skill[i];
		for (int j = i; j >= (i - k + 1) && ~j; j--) {
			cur = max(cur, skill[j]);
			/*
			 * update answer: dp[i] = max(dp[i],
			 * the skill of joining this cow to a team + all of the previous
			 * sums)
			 */
			if (j > 0) {
				dp[i] = max(dp[i], dp[j - 1] + (cur * (i - j + 1)));
			} else {
				dp[i] = max(dp[i], cur * (i - j + 1));
			}
		}
	}
	cout << dp[n - 1] << endl;
}

import java.io.*;
import java.util.*;
 
public class Teamwork {
	public static void main(String[] args) throws IOException {
		Kattio kattio = new Kattio("teamwork");
		int cows = kattio.nextInt();
		int teamSize = kattio.nextInt();
		int[] input = new int[cows];
		for (int i = 0; i < cows; i++) { input[i] = kattio.nextInt(); }
 
		/*
		 * dp[i] is the maximum sum of skill level of the first i cows,
		 * if the last team ends at index i.
		 */
		int[] dp = new int[cows];
		dp[0] = input[0];
 
		for (int right = 1; right < cows; right++) {
			// The max skill of the cows in the new team.
			int maxSkill = input[right];
			for (int left = right; left >= 0; left--) {
				int currSize = right - left + 1;
				if (currSize > teamSize) { break; }
				maxSkill = Math.max(maxSkill, input[left]);
				/*
				 * The 'new' result is the sum of the skill levels of the
				 * previous teams plus the skill level of the current team.
				 */
				if (left == 0) {
					dp[right] = Math.max(dp[right], maxSkill * currSize);
				} else {
					dp[right] = Math.max(dp[right], dp[left - 1] + maxSkill * currSize);
				}
			}
		}
		kattio.println(dp[cows - 1]);
		kattio.close();
	}
 
	// CodeSnip{Kattio}
}

n, k = map(int, input().split())
l = []
for i in range(n):
	l.append(int(input()))
 
dp = [-1] * n
dp[0] = l[0]
for i in range(n):
	# by not joining it to a team, the default value is just l[i]
	mx = l[i]
	for j in range(i, -1, -1):
		cr = i - j + 1
		if cr > k:
			break
		mx = max(mx, l[j])
		# update answer: dp[i] = max(dp[i],the skill of joining this cow to a team + all of the previous sums)
		if j == 0:
			dp[i] = max(dp[i], mx * cr)
		else:
			dp[i] = max(dp[i], dp[j - 1] + (mx * cr))
print(dp[n - 1])