Submission #1234626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234626		karen671	Feast (NOI19_feast)	C++20	59 / 100	210 ms	327680 KiB

feast

#include <chrono>
#include <iostream>
#include <random>
#include <cmath>
#include <ostream>
#include <type_traits>

constexpr int64_t inf = 100000000ll;

int main() {
    uint32_t n, k;
    std::cin >> n >> k;

    std::vector<int64_t> a(n);
    for (uint32_t i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    std::vector<std::vector<int64_t> > dm(n + 1, std::vector<int64_t>(k + 1, -inf));
    std::vector<std::vector<int64_t> > locmax(n + 1, std::vector<int64_t>(k + 1, -inf));

    dm[0][0] = 0;
    for (uint32_t i = 1; i <= n; i++) {
        for (uint32_t j = 0; j <= k; j++) {
            dm[i][j] = dm[i - 1][j];

            if (j > 0) {
                locmax[i][j] = std::max(locmax[i - 1][j] + a[i - 1],
                                        dm[i - 1][j - 1] + a[i - 1]);
                dm[i][j] = std::max(dm[i][j], locmax[i][j]);
            }
        }
    }

    int64_t maxx = -inf;
    for (uint32_t i = 0; i <= k; i++) {
        maxx = std::max(maxx, dm[n][i]);
    }

    std::cout << maxx;
    return 0;
}

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