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

• View this file on GitHub
• Last update: 2026-08-23 09:04:13+00:00
• Problem: https://judge.yosupo.jp/problem/min_plus_convolution_concave_arbitrary

Depends on

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

Code

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

#include <iostream>
#include <vector>

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

int main() {
  int N, M;
  std::cin >> N >> M;
  std::vector<int> A(N), B(M);
  for (int& a : A) std::cin >> a;
  for (int& b : B) std::cin >> b;
  auto C = min_plus_convolution_concave_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-concave-arbitrary.test.cpp"
// clang-format off
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/min_plus_convolution_concave_arbitrary
// clang-format on

#include <iostream>
#include <vector>

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

#include <algorithm>
#include <limits>
#line 6 "dp/min-plus-convolution-concave-arbitary.hpp"

#line 2 "dp/smawk.hpp"

#line 4 "dp/smawk.hpp"
#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 8 "dp/min-plus-convolution-concave-arbitary.hpp"

template <typename T>
std::vector<T> min_plus_convolution_concave_arbitary(const std::vector<T>& a,
                                                     const std::vector<T>& b) {
  if (a.empty() || b.empty()) return {};
  int N = static_cast<int>(a.size());
  int M = static_cast<int>(b.size());
  int H = N + M - 1;

  std::vector<int> column_min(H, 0), column_max(H, M - 1);
  for (int row = N; row < H; ++row) column_min[row] = row - N + 1;
  for (int row = 0; row <= H - N; ++row) column_max[row] = row;

  std::vector<int> row_min(M), row_max(M);
  for (int column = 0; column < M; ++column) {
    row_min[column] = column;
    row_max[column] = N - 1 + column;
  }

  std::vector<T> result(H, std::numeric_limits<T>::max());
  auto divide = [&](auto&& self, int row_left, int row_right, int column_left,
                    int column_right) -> void {
    if (column_max[row_left] >= column_right &&
        column_left >= column_min[row_right]) {
      auto value = [&](int row, int column) {
        int j = column_right - column;
        return b[j] + a[row_left + row - j];
      };
      auto argmin =
          smawk(row_right - row_left + 1, column_right - column_left + 1,
                [&](int row, int old_column, int new_column) {
                  return value(row, new_column) < value(row, old_column);
                });
      for (int row = row_left; row <= row_right; ++row) {
        result[row] = std::min(result[row],
                               value(row - row_left, argmin[row - row_left]));
      }
      return;
    }

    if (row_right - row_left > column_right - column_left) {
      int row_middle = (row_left + row_right) / 2;
      int next_column_right = std::min(column_max[row_middle], column_right);
      if (column_left <= next_column_right) {
        self(self, row_left, row_middle, column_left, next_column_right);
      }
      int next_column_left = std::max(column_min[row_middle], column_left);
      if (next_column_left <= column_right) {
        self(self, row_middle + 1, row_right, next_column_left, column_right);
      }
    } else {
      int column_middle = (column_left + column_right) / 2;
      int next_row_right = std::min(row_max[column_middle], row_right);
      if (row_left <= next_row_right) {
        self(self, row_left, next_row_right, column_left, column_middle);
      }
      int next_row_left = std::max(row_min[column_middle], row_left);
      if (next_row_left <= row_right) {
        self(self, next_row_left, row_right, column_middle + 1, column_right);
      }
    }
  };
  divide(divide, 0, H - 1, 0, M - 1);
  return result;
}
#line 9 "test/verify/yosupo-min-plus-convolution-concave-arbitrary.test.cpp"

int main() {
  int N, M;
  std::cin >> N >> M;
  std::vector<int> A(N), B(M);
  for (int& a : A) std::cin >> a;
  for (int& b : B) std::cin >> b;
  auto C = min_plus_convolution_concave_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	2 ms	4 MB
g++	hack_00	AC	2 ms	3 MB
g++	large_small_00	AC	196 ms	18 MB
g++	large_small_01	AC	204 ms	13 MB
g++	large_small_02	AC	239 ms	16 MB
g++	large_small_03	AC	258 ms	16 MB
g++	max_random_00	AC	714 ms	28 MB
g++	max_random_01	AC	684 ms	28 MB
g++	max_random_02	AC	706 ms	28 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	603 ms	28 MB
g++	monotone_01	AC	664 ms	29 MB
g++	monotone_02	AC	665 ms	29 MB
g++	monotone_03	AC	712 ms	30 MB
g++	near_power_of_2_00	AC	345 ms	16 MB
g++	near_power_of_2_01	AC	350 ms	16 MB
g++	near_power_of_2_02	AC	343 ms	16 MB
g++	near_power_of_2_03	AC	349 ms	16 MB
g++	near_power_of_2_04	AC	360 ms	16 MB
g++	near_power_of_2_05	AC	370 ms	16 MB
g++	near_power_of_2_06	AC	381 ms	16 MB
g++	near_power_of_2_07	AC	358 ms	16 MB
g++	near_power_of_2_08	AC	358 ms	16 MB
g++	only_first_small_00	AC	720 ms	28 MB
g++	only_first_small_01	AC	689 ms	28 MB
g++	random_00	AC	549 ms	22 MB
g++	random_01	AC	610 ms	24 MB
g++	random_02	AC	386 ms	14 MB
g++	small_00	AC	2 ms	3 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	4 MB
g++	small_05	AC	2 ms	4 MB
g++	small_06	AC	2 ms	4 MB
g++	small_07	AC	2 ms	4 MB
g++	small_08	AC	2 ms	4 MB
g++	small_slopes_00	AC	707 ms	28 MB
g++	small_slopes_01	AC	677 ms	28 MB
clang++	example_00	AC	2 ms	4 MB
clang++	hack_00	AC	2 ms	4 MB
clang++	large_small_00	AC	196 ms	18 MB
clang++	large_small_01	AC	184 ms	13 MB
clang++	large_small_02	AC	229 ms	16 MB
clang++	large_small_03	AC	250 ms	16 MB
clang++	max_random_00	AC	670 ms	28 MB
clang++	max_random_01	AC	673 ms	28 MB
clang++	max_random_02	AC	707 ms	28 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	622 ms	28 MB
clang++	monotone_01	AC	672 ms	29 MB
clang++	monotone_02	AC	668 ms	29 MB
clang++	monotone_03	AC	670 ms	30 MB
clang++	near_power_of_2_00	AC	335 ms	16 MB
clang++	near_power_of_2_01	AC	344 ms	16 MB
clang++	near_power_of_2_02	AC	337 ms	16 MB
clang++	near_power_of_2_03	AC	356 ms	16 MB
clang++	near_power_of_2_04	AC	339 ms	16 MB
clang++	near_power_of_2_05	AC	369 ms	16 MB
clang++	near_power_of_2_06	AC	360 ms	16 MB
clang++	near_power_of_2_07	AC	349 ms	16 MB
clang++	near_power_of_2_08	AC	356 ms	16 MB
clang++	only_first_small_00	AC	705 ms	28 MB
clang++	only_first_small_01	AC	670 ms	28 MB
clang++	random_00	AC	578 ms	22 MB
clang++	random_01	AC	593 ms	24 MB
clang++	random_02	AC	376 ms	14 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	670 ms	28 MB
clang++	small_slopes_01	AC	654 ms	28 MB

Back to top page