Submission #1097171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097171		crafticat	Feast (NOI19_feast)	C++17	0 / 100	261 ms	262144 KiB

feast

#include "bits/stdc++.h"

using namespace std;
template<typename T>
using V = vector<T>;
#define ckmax(a,b) a= max(a,b)

int solve(V<int>&arr, int k, int p) {
    V<V<V<int>>> dp(arr.size() + 1, V<V<int>>(k + 1, V<int>(2, -1e9)));
    dp[0][0][1] = 0;

    for (int i = 1; i <= arr.size(); ++i) {
        dp[i][0][1] = 0;
        for (int j = 1; j <= k; ++j) {
            for (int l = 0; l < 2; ++l) {
                dp[i][j][l] = max(dp[i - 1][j - 1][1], dp[i - 1][j][1]);
                if (l == 0) ckmax(dp[i][j][l], dp[i - 1][j][0]);
                ckmax(dp[i][j][l], dp[i - 1][j - 1][0]);
                if (l == 1) dp[i][j][l] += arr[i - 1];
            }
        }
    }

    return max(dp[arr.size()][k][0], dp[arr.size()][k][1]);
}

int main() {
    int n, k; cin >> n >> k;

    V<int> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    cout << solve(arr,k,1);

}

Compilation message (stderr)

feast.cpp: In function 'int solve(V<int>&, int, int)':
feast.cpp:12:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for (int i = 1; i <= arr.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 18
• Subtask 4: 0 / 10
• Subtask 5: 0 / 11
• Subtask 6: 0 / 20
• Subtask 7: 0 / 29