verify/yukicoder-3322.test.cpp

View this file on GitHub
Last update: 2026-07-11 16:54:42+09:00
Problem: https://yukicoder.me/problems/no/3322

Depends on

列の隣り合わない $k$ 個の要素を選んだ総和の最大値または最小値の列挙 (other/enumerate-maximum-independent-set-path-sums.hpp)

Code

// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/3322

#include <cassert>
#include <cstddef>
#include <iostream>
#include <utility>
#include <vector>

#include "../other/enumerate-maximum-independent-set-path-sums.hpp"

long long solve(const std::vector<long long> &a,
                const std::vector<long long> &b, const int k) {
    const int n = static_cast<int>(a.size());
    long long answer = 0;
    std::vector<std::pair<int, long long>> blocks;

    const auto add_block = [&](const int side, const long long cost) {
        if (!blocks.empty() && blocks.back().first == side) {
            blocks.back().second += cost;
        } else {
            blocks.push_back(std::pair<int, long long>(side, cost));
        }
    };

    add_block(0, 0);
    for (int i = 0; i < n; i += 1) {
        const std::size_t j = static_cast<std::size_t>(i);
        if (a[j] >= b[j]) {
            answer += a[j];
            add_block(0, a[j] - b[j]);
        } else {
            answer += b[j];
            add_block(1, b[j] - a[j]);
        }
    }
    add_block(k % 2, 0);

    const int transitions = static_cast<int>(blocks.size() - 1);
    int remove_count = 0;
    if (transitions > k) {
        assert((transitions - k) % 2 == 0);
        remove_count = (transitions - k) / 2;
    }

    std::vector<long long> penalties;
    penalties.reserve(blocks.size());
    for (std::size_t i = 1; i + 1 < blocks.size(); i += 1) {
        penalties.push_back(-blocks[i].second);
    }

    const std::vector<long long> best =
        enumerate_maximum_independent_set_path_sums(penalties);
    assert(0 <= remove_count &&
           static_cast<std::size_t>(remove_count) < best.size());
    return answer + best[static_cast<std::size_t>(remove_count)];
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;
    for (int case_id = 0; case_id < t; case_id += 1) {
        int n;
        int k;
        std::cin >> n >> k;
        std::vector<long long> a(static_cast<std::size_t>(n)),
            b(static_cast<std::size_t>(n));
        for (int i = 0; i < n; i += 1) {
            std::cin >> a[static_cast<std::size_t>(i)];
        }
        for (int i = 0; i < n; i += 1) {
            std::cin >> b[static_cast<std::size_t>(i)];
        }
        std::cout << solve(a, b, k) << '\n';
    }

    return 0;
}

#line 1 "verify/yukicoder-3322.test.cpp"
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/3322

#include <cassert>
#include <cstddef>
#include <iostream>
#include <utility>
#include <vector>

#line 1 "other/enumerate-maximum-independent-set-path-sums.hpp"



// 長さ n の列から隣り合わない k 個を選ぶ総和の最大値または最小値を全ての k について求める。
// 符号なし整数型は使用できない。
// 比較ソートによる実装は O(n log n)、バケットソートによる実装は非負整数列の総和を S として O(n + S)。

#include <algorithm>
#line 11 "other/enumerate-maximum-independent-set-path-sums.hpp"
#include <cstdint>
#include <limits>
#include <type_traits>
#line 16 "other/enumerate-maximum-independent-set-path-sums.hpp"

namespace enumerate_maximum_independent_set_path_sums_internal {
template <bool maximum, class T>
bool removable_side(const std::pair<bool, T> &side,
                    const std::pair<bool, T> &center) {
    if (!side.first) {
        return true;
    }
    if (!center.first) {
        return false;
    }
    if constexpr (maximum) {
        return !(center.second < side.second);
    } else {
        return !(side.second < center.second);
    }
}

template <class T, bool maximum>
std::vector<T> marginal_values(const std::vector<T> &a) {
    using P = std::pair<bool, T>;
    const P none(false, T());
    std::vector<P> stack;
    std::vector<T> res;
    stack.reserve(a.size() + 2);
    res.reserve((a.size() + 1) / 2);
    stack.push_back(none);

    const auto add = [&](P x) {
        while (stack.size() >= 2 && stack.back().first &&
               removable_side<maximum>(x, stack.back()) &&
               removable_side<maximum>(stack[stack.size() - 2], stack.back())) {
            P l = std::move(stack[stack.size() - 2]);
            P p = std::move(stack.back());
            x = l.first && x.first ? P(true, l.second - p.second + x.second)
                                   : none;
            res.push_back(std::move(p.second));
            stack.pop_back();
            stack.pop_back();
        }
        stack.push_back(x);
    };

    for (const T &x : a) {
        add(P(true, x));
    }
    add(none);
    return res;
}

// x の絶対値が offset 以下であることを呼び出し元で保証する。
template <class T>
std::size_t bucket_index(const T x, const std::size_t offset) {
    if (T(0) <= x) {
        return offset + static_cast<std::size_t>(x);
    }
    return offset - static_cast<std::size_t>(T(0) - x);
}

template <class T>
T bucket_value(const std::size_t index, const std::size_t offset) {
    if (offset <= index) {
        return static_cast<T>(index - offset);
    }
    return T(0) - static_cast<T>(offset - index);
}
} // namespace enumerate_maximum_independent_set_path_sums_internal

template <class T, bool maximum = true>
std::vector<T>
enumerate_maximum_independent_set_path_sums(const std::vector<T> &a) {
    static_assert(!std::is_unsigned_v<T>,
                  "T must not be an unsigned type in "
                  "enumerate_maximum_independent_set_path_sums.");

    std::vector<T> xs =
        enumerate_maximum_independent_set_path_sums_internal::marginal_values<
            T, maximum>(a);
    std::sort(xs.begin(), xs.end(), [](const T &x, const T &y) {
        if constexpr (maximum) {
            return y < x;
        } else {
            return x < y;
        }
    });
    std::vector<T> res(1, T());
    res.reserve(xs.size() + 1);
    T sum = T();
    for (const T &x : xs) {
        sum += x;
        res.push_back(sum);
    }
    return res;
}

template <bool maximum, class T>
std::vector<T>
enumerate_maximum_independent_set_path_sums(const std::vector<T> &a) {
    return enumerate_maximum_independent_set_path_sums<T, maximum>(a);
}

template <class T, bool maximum = true>
std::vector<T> enumerate_maximum_independent_set_path_sums_bucket_sort(
    const std::vector<T> &a) {
    static_assert(!std::is_unsigned_v<T>,
                  "T must not be an unsigned type in "
                  "enumerate_maximum_independent_set_path_sums_bucket_sort.");
    static_assert(
        std::is_integral_v<T> && std::is_signed_v<T> &&
            !std::is_same_v<T, bool> && sizeof(T) <= sizeof(std::int32_t),
        "T must be a non-bool signed integral type of at most 32 bits in "
        "enumerate_maximum_independent_set_path_sums_bucket_sort.");

    T total = T();
    for (const T &x : a) {
        assert(T(0) <= x);
        assert(x <= std::numeric_limits<T>::max() - total);
        total += x;
    }

    const std::vector<T> xs =
        enumerate_maximum_independent_set_path_sums_internal::marginal_values<
            T, maximum>(a);
    const std::size_t offset = static_cast<std::size_t>(total);
    assert(offset <= (std::numeric_limits<std::size_t>::max() - 1) / 2);
    std::vector<std::size_t> count(offset * 2 + 1, 0);
    for (const T &x : xs) {
        count[enumerate_maximum_independent_set_path_sums_internal::
                  bucket_index(x, offset)] += 1;
    }

    std::vector<T> res(1, T());
    res.reserve(xs.size() + 1);
    T sum = T();
    if constexpr (maximum) {
        for (std::size_t index_plus_one = count.size(); index_plus_one > 0;
             index_plus_one -= 1) {
            const std::size_t index = index_plus_one - 1;
            const std::size_t c = count[index];
            if (c == 0) {
                continue;
            }
            const T x = enumerate_maximum_independent_set_path_sums_internal::
                bucket_value<T>(index, offset);
            for (std::size_t i = 0; i < c; i += 1) {
                sum += x;
                res.push_back(sum);
            }
        }
    } else {
        for (std::size_t index = 0; index < count.size(); index += 1) {
            const std::size_t c = count[index];
            if (c == 0) {
                continue;
            }
            const T x = enumerate_maximum_independent_set_path_sums_internal::
                bucket_value<T>(index, offset);
            for (std::size_t i = 0; i < c; i += 1) {
                sum += x;
                res.push_back(sum);
            }
        }
    }
    return res;
}

template <bool maximum, class T>
std::vector<T> enumerate_maximum_independent_set_path_sums_bucket_sort(
    const std::vector<T> &a) {
    return enumerate_maximum_independent_set_path_sums_bucket_sort<T, maximum>(
        a);
}


#line 10 "verify/yukicoder-3322.test.cpp"

long long solve(const std::vector<long long> &a,
                const std::vector<long long> &b, const int k) {
    const int n = static_cast<int>(a.size());
    long long answer = 0;
    std::vector<std::pair<int, long long>> blocks;

    const auto add_block = [&](const int side, const long long cost) {
        if (!blocks.empty() && blocks.back().first == side) {
            blocks.back().second += cost;
        } else {
            blocks.push_back(std::pair<int, long long>(side, cost));
        }
    };

    add_block(0, 0);
    for (int i = 0; i < n; i += 1) {
        const std::size_t j = static_cast<std::size_t>(i);
        if (a[j] >= b[j]) {
            answer += a[j];
            add_block(0, a[j] - b[j]);
        } else {
            answer += b[j];
            add_block(1, b[j] - a[j]);
        }
    }
    add_block(k % 2, 0);

    const int transitions = static_cast<int>(blocks.size() - 1);
    int remove_count = 0;
    if (transitions > k) {
        assert((transitions - k) % 2 == 0);
        remove_count = (transitions - k) / 2;
    }

    std::vector<long long> penalties;
    penalties.reserve(blocks.size());
    for (std::size_t i = 1; i + 1 < blocks.size(); i += 1) {
        penalties.push_back(-blocks[i].second);
    }

    const std::vector<long long> best =
        enumerate_maximum_independent_set_path_sums(penalties);
    assert(0 <= remove_count &&
           static_cast<std::size_t>(remove_count) < best.size());
    return answer + best[static_cast<std::size_t>(remove_count)];
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;
    for (int case_id = 0; case_id < t; case_id += 1) {
        int n;
        int k;
        std::cin >> n >> k;
        std::vector<long long> a(static_cast<std::size_t>(n)),
            b(static_cast<std::size_t>(n));
        for (int i = 0; i < n; i += 1) {
            std::cin >> a[static_cast<std::size_t>(i)];
        }
        for (int i = 0; i < n; i += 1) {
            std::cin >> b[static_cast<std::size_t>(i)];
        }
        std::cout << solve(a, b, k) << '\n';
    }

    return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	corner_01	AC	98 ms	12 MB
g++	corner_02	AC	98 ms	13 MB
g++	corner_03	AC	98 ms	13 MB
g++	corner_04	AC	98 ms	12 MB
g++	corner_05	AC	102 ms	13 MB
g++	corner_06	AC	98 ms	12 MB
g++	corner_07	AC	35 ms	6 MB
g++	corner_08	AC	35 ms	6 MB
g++	corner_09	AC	35 ms	6 MB
g++	corner_10	AC	36 ms	6 MB
g++	corner_11	AC	35 ms	6 MB
g++	corner_12	AC	35 ms	6 MB
g++	killer_01	AC	101 ms	13 MB
g++	random_01	AC	78 ms	9 MB
g++	random_02	AC	77 ms	9 MB
g++	random_03	AC	78 ms	9 MB
g++	random_04	AC	77 ms	9 MB
g++	random_05	AC	77 ms	9 MB
g++	random_06	AC	73 ms	4 MB
g++	random_07	AC	73 ms	4 MB
g++	random_08	AC	73 ms	4 MB
g++	random_09	AC	73 ms	4 MB
g++	random_10	AC	73 ms	4 MB
g++	random_11	AC	70 ms	4 MB
g++	random_12	AC	67 ms	4 MB
g++	random_13	AC	68 ms	4 MB
g++	random_14	AC	68 ms	4 MB
g++	random_15	AC	67 ms	3 MB
g++	random_16	AC	68 ms	3 MB
g++	random_17	AC	68 ms	4 MB
g++	random_18	AC	68 ms	4 MB
g++	random_19	AC	69 ms	4 MB
g++	random_20	AC	68 ms	4 MB
g++	random_21	AC	88 ms	4 MB
g++	random_22	AC	86 ms	3 MB
g++	random_23	AC	87 ms	4 MB
g++	random_24	AC	86 ms	4 MB
g++	random_25	AC	85 ms	4 MB
g++	random_26	AC	214 ms	3 MB
g++	random_27	AC	216 ms	4 MB
g++	random_28	AC	215 ms	3 MB
g++	random_29	AC	214 ms	3 MB
g++	random_30	AC	214 ms	3 MB
g++	sample_01	AC	3 ms	3 MB
clang++	corner_01	AC	102 ms	13 MB
clang++	corner_02	AC	100 ms	12 MB
clang++	corner_03	AC	101 ms	13 MB
clang++	corner_04	AC	100 ms	13 MB
clang++	corner_05	AC	100 ms	12 MB
clang++	corner_06	AC	100 ms	13 MB
clang++	corner_07	AC	43 ms	6 MB
clang++	corner_08	AC	43 ms	6 MB
clang++	corner_09	AC	43 ms	6 MB
clang++	corner_10	AC	43 ms	6 MB
clang++	corner_11	AC	44 ms	6 MB
clang++	corner_12	AC	43 ms	6 MB
clang++	killer_01	AC	106 ms	13 MB
clang++	random_01	AC	83 ms	9 MB
clang++	random_02	AC	82 ms	9 MB
clang++	random_03	AC	81 ms	9 MB
clang++	random_04	AC	82 ms	9 MB
clang++	random_05	AC	83 ms	9 MB
clang++	random_06	AC	77 ms	4 MB
clang++	random_07	AC	77 ms	4 MB
clang++	random_08	AC	78 ms	4 MB
clang++	random_09	AC	77 ms	4 MB
clang++	random_10	AC	78 ms	4 MB
clang++	random_11	AC	72 ms	4 MB
clang++	random_12	AC	74 ms	4 MB
clang++	random_13	AC	72 ms	4 MB
clang++	random_14	AC	72 ms	4 MB
clang++	random_15	AC	72 ms	4 MB
clang++	random_16	AC	71 ms	4 MB
clang++	random_17	AC	72 ms	4 MB
clang++	random_18	AC	71 ms	4 MB
clang++	random_19	AC	71 ms	4 MB
clang++	random_20	AC	71 ms	4 MB
clang++	random_21	AC	90 ms	3 MB
clang++	random_22	AC	88 ms	3 MB
clang++	random_23	AC	89 ms	3 MB
clang++	random_24	AC	88 ms	4 MB
clang++	random_25	AC	89 ms	3 MB
clang++	random_26	AC	221 ms	4 MB
clang++	random_27	AC	219 ms	4 MB
clang++	random_28	AC	221 ms	3 MB
clang++	random_29	AC	223 ms	4 MB
clang++	random_30	AC	218 ms	3 MB
clang++	sample_01	AC	3 ms	3 MB