oj.uz

Submission #898958

# Submission time Handle Problem Language Result Execution time Memory
898958 2024-01-05T10:04:05 Z y_combinator Nafta (COI15_nafta) C++17
100 / 100
 311 ms 152660 KB 
#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 pfxs = std::vector<std::vector<int>>(s + 1, std::vector<int>(s));

    for (auto i = 0; i < s; ++i) {
        for (auto j = 0; j < s; ++j) {
            pfxs[i + 1][j] = pfxs[i][j] + sums[i][j];
        }
    }

    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;
                for (auto i = opt_mn; i <= std::min(opt_mx, idx_m); ++i) {
                    if (dp[i - 1] == -1) {
                        continue;
                    }
                    const auto val = dp[i - 1] + pfxs[idx_m][idx_m - 1] - pfxs[i - 1][idx_m - 1];
                    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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 600 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Correct 4 ms 1116 KB Output is correct
8 Correct 5 ms 1116 KB Output is correct
9 Correct 8 ms 3932 KB Output is correct
10 Correct 4 ms 1116 KB Output is correct
11 Correct 3 ms 1116 KB Output is correct
12 Correct 3 ms 1116 KB Output is correct

Subtask #3
66.0 / 66.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Correct 4 ms 1116 KB Output is correct
8 Correct 5 ms 1116 KB Output is correct
9 Correct 8 ms 3932 KB Output is correct
10 Correct 4 ms 1116 KB Output is correct
11 Correct 3 ms 1116 KB Output is correct
12 Correct 3 ms 1116 KB Output is correct
13 Correct 168 ms 36772 KB Output is correct
14 Correct 212 ms 40612 KB Output is correct
15 Correct 311 ms 152660 KB Output is correct
16 Correct 143 ms 40608 KB Output is correct
17 Correct 129 ms 40532 KB Output is correct
18 Correct 128 ms 40532 KB Output is correct