oj.uz

Submission #1097171

# Submission time Handle Problem Language Result Execution time Memory
1097171 2024-10-06T11:14:28 Z crafticat Feast (NOI19_feast) C++17
0 / 100
 261 ms 262144 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 261 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 46160 KB Output is correct
2 Correct 85 ms 47160 KB Output is correct
3 Correct 84 ms 45960 KB Output is correct
4 Runtime error 215 ms 262144 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 118 ms 48468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 261 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -