USACO 2018 Gold December Q3. Teamwork

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <bits/stdc++.h>
using namespace std;

int N, K;


int main() {
    ifstream cin("teamwork.in");
    ofstream cout("teamwork.out");

    cin >> N >> K;

    vector<int> cows(N);
    vector<int> dp(N);
    for (int i = 0; i < N; i++) {
        cin >> cows[i];
        dp[i] = cows[i];
    }

    for (int i = 1; i < N; i++) {
        int currMax = cows[i];
        for (int k = 0; k < K; k++) {
            // range from j --> i
            int j = i - k;
            if (j < 0) {
                break;
            }
            currMax = max(currMax, cows[j]);
            dp[i] = max(dp[i], dp[j - 1] + (currMax * (k + 1)));
        }
    }

    cout << dp[N - 1];
}