test/verify/yosupo-min-plus-convolution-convex-arbitrary.test.cpp

• View this file on GitHub
• Last update: 2026-08-23 08:59:58+00:00
• Problem: https://judge.yosupo.jp/problem/min_plus_convolution_convex_arbitrary

Depends on

• Min Plus Convolution (Convex and Arbitary) (dp/min-plus-convolution-convex-arbitary.hpp)
• SMAWK (dp/smawk.hpp)

Code

// clang-format off
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/min_plus_convolution_convex_arbitrary
// clang-format on

#include <iostream>
#include <vector>

#include "../../dp/min-plus-convolution-convex-arbitary.hpp"

int main() {
  int N, M;
  std::cin >> N >> M;
  std::vector<long long> A(N), B(M);
  for (long long& a : A) std::cin >> a;
  for (long long& b : B) std::cin >> b;
  auto C = min_plus_convolution_convex_arbitary(A, B);
  for (int i = 0; i < static_cast<int>(C.size()); ++i) {
    if (i) std::cout << ' ';
    std::cout << C[i];
  }
  std::cout << '\n';
}

#line 1 "test/verify/yosupo-min-plus-convolution-convex-arbitrary.test.cpp"
// clang-format off
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/min_plus_convolution_convex_arbitrary
// clang-format on

#include <iostream>
#include <vector>

#line 2 "dp/min-plus-convolution-convex-arbitary.hpp"

#line 4 "dp/min-plus-convolution-convex-arbitary.hpp"

#line 2 "dp/smawk.hpp"

#include <algorithm>
#include <numeric>
#line 6 "dp/smawk.hpp"

template <typename F>
std::vector<int> smawk(int H, int W, F comp) {
  std::vector<int> ret(H, -1);
  if (H == 0 || W == 0) return ret;

  auto dfs = [&](auto&& self, const std::vector<int>& rows,
                 const std::vector<int>& cols) -> void {
    if (rows.empty()) return;
    std::vector<int> reduced;
    reduced.reserve(std::min(rows.size(), cols.size()));
    for (int c : cols) {
      while (!reduced.empty()) {
        int r = rows[reduced.size() - 1];
        int old_c = reduced.back();
        if (comp(r, old_c, c)) {
          reduced.pop_back();
        } else {
          break;
        }
      }
      if (reduced.size() < rows.size()) reduced.emplace_back(c);
    }

    std::vector<int> odd_rows;
    odd_rows.reserve(rows.size() / 2);
    for (int i = 1; i < static_cast<int>(rows.size()); i += 2) {
      odd_rows.emplace_back(rows[i]);
    }
    self(self, odd_rows, reduced);

    int left = 0;
    for (int i = 0; i < static_cast<int>(rows.size()); i += 2) {
      int right = static_cast<int>(reduced.size()) - 1;
      if (i + 1 < static_cast<int>(rows.size())) {
        right = left;
        while (reduced[right] != ret[rows[i + 1]]) ++right;
      }
      int best = left;
      for (int p = left + 1; p <= right; ++p) {
        if (comp(rows[i], reduced[best], reduced[p])) best = p;
      }
      ret[rows[i]] = reduced[best];
      left = right;
    }
  };

  std::vector<int> rows(H), cols(W);
  std::iota(rows.begin(), rows.end(), 0);
  std::iota(cols.begin(), cols.end(), 0);
  dfs(dfs, rows, cols);
  return ret;
}
#line 6 "dp/min-plus-convolution-convex-arbitary.hpp"

template <typename T>
std::vector<T> min_plus_convolution_convex_arbitary(const std::vector<T>& a,
                                                    const std::vector<T>& b) {
  if (a.empty() || b.empty()) return {};
  int H = static_cast<int>(a.size());
  int W = static_cast<int>(b.size());
  const auto c = smawk(H + W - 1, W, [&](int i, int j, int k) {
    if (i < k) return false;
    if (i - j >= H) return true;
    return b[k] + a[i - k] < b[j] + a[i - j];
  });
  std::vector<T> ret;
  ret.reserve(H + W - 1);
  for (int i = 0; i < H + W - 1; ++i) {
    ret.emplace_back(b[c[i]] + a[i - c[i]]);
  }
  return ret;
}
#line 9 "test/verify/yosupo-min-plus-convolution-convex-arbitrary.test.cpp"

int main() {
  int N, M;
  std::cin >> N >> M;
  std::vector<long long> A(N), B(M);
  for (long long& a : A) std::cin >> a;
  for (long long& b : B) std::cin >> b;
  auto C = min_plus_convolution_convex_arbitary(A, B);
  for (int i = 0; i < static_cast<int>(C.size()); ++i) {
    if (i) std::cout << ' ';
    std::cout << C[i];
  }
  std::cout << '\n';
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	3 ms	3 MB
g++	hack_00	AC	2 ms	4 MB
g++	large_small_00	AC	192 ms	14 MB
g++	large_small_01	AC	173 ms	14 MB
g++	large_small_02	AC	189 ms	20 MB
g++	large_small_03	AC	210 ms	20 MB
g++	max_random_00	AC	369 ms	30 MB
g++	max_random_01	AC	369 ms	30 MB
g++	max_random_02	AC	363 ms	30 MB
g++	med_random_00	AC	3 ms	4 MB
g++	med_random_01	AC	2 ms	4 MB
g++	med_random_02	AC	2 ms	4 MB
g++	monotone_00	AC	367 ms	31 MB
g++	monotone_01	AC	362 ms	32 MB
g++	monotone_02	AC	388 ms	30 MB
g++	monotone_03	AC	365 ms	31 MB
g++	near_power_of_2_00	AC	186 ms	17 MB
g++	near_power_of_2_01	AC	185 ms	17 MB
g++	near_power_of_2_02	AC	188 ms	17 MB
g++	near_power_of_2_03	AC	188 ms	17 MB
g++	near_power_of_2_04	AC	192 ms	17 MB
g++	near_power_of_2_05	AC	187 ms	17 MB
g++	near_power_of_2_06	AC	207 ms	17 MB
g++	near_power_of_2_07	AC	184 ms	17 MB
g++	near_power_of_2_08	AC	201 ms	17 MB
g++	only_first_small_00	AC	370 ms	30 MB
g++	only_first_small_01	AC	407 ms	30 MB
g++	random_00	AC	311 ms	24 MB
g++	random_01	AC	312 ms	25 MB
g++	random_02	AC	174 ms	16 MB
g++	small_00	AC	2 ms	4 MB
g++	small_01	AC	2 ms	4 MB
g++	small_02	AC	2 ms	4 MB
g++	small_03	AC	2 ms	4 MB
g++	small_04	AC	2 ms	3 MB
g++	small_05	AC	2 ms	3 MB
g++	small_06	AC	2 ms	4 MB
g++	small_07	AC	2 ms	3 MB
g++	small_08	AC	2 ms	4 MB
g++	small_slopes_00	AC	389 ms	30 MB
g++	small_slopes_01	AC	369 ms	30 MB
clang++	example_00	AC	3 ms	4 MB
clang++	hack_00	AC	2 ms	4 MB
clang++	large_small_00	AC	180 ms	14 MB
clang++	large_small_01	AC	185 ms	14 MB
clang++	large_small_02	AC	186 ms	20 MB
clang++	large_small_03	AC	202 ms	20 MB
clang++	max_random_00	AC	405 ms	30 MB
clang++	max_random_01	AC	379 ms	30 MB
clang++	max_random_02	AC	362 ms	30 MB
clang++	med_random_00	AC	3 ms	4 MB
clang++	med_random_01	AC	2 ms	4 MB
clang++	med_random_02	AC	2 ms	4 MB
clang++	monotone_00	AC	365 ms	31 MB
clang++	monotone_01	AC	356 ms	32 MB
clang++	monotone_02	AC	391 ms	30 MB
clang++	monotone_03	AC	401 ms	31 MB
clang++	near_power_of_2_00	AC	204 ms	17 MB
clang++	near_power_of_2_01	AC	201 ms	17 MB
clang++	near_power_of_2_02	AC	186 ms	17 MB
clang++	near_power_of_2_03	AC	205 ms	17 MB
clang++	near_power_of_2_04	AC	202 ms	17 MB
clang++	near_power_of_2_05	AC	206 ms	17 MB
clang++	near_power_of_2_06	AC	188 ms	17 MB
clang++	near_power_of_2_07	AC	197 ms	17 MB
clang++	near_power_of_2_08	AC	185 ms	17 MB
clang++	only_first_small_00	AC	373 ms	30 MB
clang++	only_first_small_01	AC	372 ms	30 MB
clang++	random_00	AC	320 ms	24 MB
clang++	random_01	AC	312 ms	25 MB
clang++	random_02	AC	160 ms	16 MB
clang++	small_00	AC	2 ms	4 MB
clang++	small_01	AC	2 ms	4 MB
clang++	small_02	AC	2 ms	4 MB
clang++	small_03	AC	2 ms	4 MB
clang++	small_04	AC	2 ms	4 MB
clang++	small_05	AC	2 ms	4 MB
clang++	small_06	AC	2 ms	4 MB
clang++	small_07	AC	2 ms	4 MB
clang++	small_08	AC	2 ms	4 MB
clang++	small_slopes_00	AC	383 ms	30 MB
clang++	small_slopes_01	AC	392 ms	30 MB

Back to top page