Submission #898954

#	Time	Username	Problem	Language	Result	Execution time	Memory
898954		y_combinator	Nafta (COI15_nafta)	C++17	34 / 100	1043 ms	24996 KiB

nafta

#include <algorithm>
#include <array>
#include <ios>
#include <iostream>
#include <numeric>
#include <string>
#include <utility>
#include <vector>

template <typename F>
class YCombinator {

private:

    const F f = nullptr;

public:

    explicit YCombinator(F&& f) : f(f) {}

    template <typename... Ts>
    decltype(auto) operator()(Ts&&... arguments) const {

        return f(*this, std::forward<Ts>(arguments)...);

    }

};

template <typename F>
YCombinator(F) -> YCombinator<F>;

constexpr auto dir_1 = std::array<int, 4>({1, 0, -1, 0});
constexpr auto dir_2 = std::array<int, 4>({0, 1, 0, -1});

auto solve() {

    auto r = 0;
    auto s = 0;

    std::cin >> r >> s;

    auto amts = std::vector<std::string>(r);

    for (auto& x : amts) {
        std::cin >> x;
    }

    auto sums = std::vector<std::vector<int>>(s, std::vector<int>(s + 1));
    auto vis = std::vector<std::vector<bool>>(r, std::vector<bool>(s));

    for (auto i = 0; i < r; ++i) {
        for (auto j = 0; j < s; ++j) {
            const auto canVisit = [&](int row, int col) {
                return (
                    row >= 0 && row < r && col >= 0 && col < s && !vis[row][col] &&
                    amts[row][col] != '.'
                );
            };
            if (!canVisit(i, j)) {
                continue;
            }
            auto col_mn = s;
            auto col_mx = -1;
            auto sum = 0;
            YCombinator(
                [&](auto self, int row, int col) -> void {
                    sum += amts[row][col] - '0';
                    vis[row][col] = true;
                    col_mn = std::min(col_mn, col);
                    col_mx = std::max(col_mx, col);
                    for (auto i = 0; i < 4; ++i) {
                        const auto new_col = col + dir_1[i];
                        const auto new_row = row + dir_2[i];
                        if (canVisit(new_row, new_col)) {
                            self(new_row, new_col);
                        }
                    }
                }
            )(i, j);
            sums[col_mn][col_mn] += sum;
            sums[col_mn][col_mx + 1] -= sum;
        }
    }

    for (auto& x : sums) {
        std::partial_sum(x.begin(), x.end(), x.begin());
    }

    auto dp = std::vector<int>(s + 1, -1);

    dp[0] = 0;

    for (auto i = 1; i <= s; ++i) {
        auto new_dp = std::vector<int>(s + 1, -1);
        YCombinator(
            [&](auto self, int idx_l, int idx_r, int opt_mn, int opt_mx) -> void {
                const auto idx_m = (idx_l + idx_r) >> 1;
                auto opt = opt_mn;
                auto sum = 0;
                for (auto i = idx_m; i > opt_mx; --i) {
                    sum += sums[i - 1][idx_m - 1];
                }
                for (auto i = std::min(opt_mx, idx_m); i >= opt_mn; --i) {
                    sum += sums[i - 1][idx_m - 1];
                    if (dp[i - 1] == -1) {
                        continue;
                    }
                    const auto val = dp[i - 1] + sum;
                    if (val < new_dp[idx_m] && new_dp[idx_m] != -1) {
                        continue;
                    }
                    new_dp[idx_m] = val;
                    opt = i;
                }
                if (idx_l < idx_m) {
                    self(idx_l, idx_m - 1, opt_mn, opt);
                }
                if (idx_r > idx_m) {
                    self(idx_m + 1, idx_r, opt, opt_mx);
                }
            }
        )(1, s, 1, s);
        dp = new_dp;
        std::cout << *std::max_element(dp.begin(), dp.end()) << '\n';
    }

}

auto main() -> int {

    std::cin.tie(nullptr);

    std::ios_base::sync_with_stdio(false);

    solve();

    return 0;

}

• Subtask 1: 11 / 11
• Subtask 2: 23 / 23
• Subtask 3: 0 / 66