test/yosupo/min_plus_convolution_convex_arbitrary.monotone_minima.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 12:11:12+09:00
• Problem: https://judge.yosupo.jp/problem/min_plus_convolution_convex_arbitrary

Depends on

• monotone minima (src/Optimization/monotone_minima.hpp)

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/min_plus_convolution_convex_arbitrary
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include "src/Optimization/monotone_minima.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, M;
 cin >> N >> M;
 long long a[N], b[M];
 for (int i= 0; i < N; ++i) cin >> a[i];
 for (int j= 0; j < M; ++j) cin >> b[j];
 auto select= [&](int i, int j, int k) {
  if (i < k) return false;
  if (i - j >= N) return true;
  return a[i - j] + b[j] >= a[i - k] + b[k];
 };
 auto r= monotone_minima(N + M - 1, M, select);
 for (int i= 0; i < N + M - 1; ++i) cout << a[i - r[i]] + b[r[i]] << " \n"[i == N + M - 2];
 return 0;
}

#line 1 "test/yosupo/min_plus_convolution_convex_arbitrary.monotone_minima.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/min_plus_convolution_convex_arbitrary
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#line 2 "src/Optimization/monotone_minima.hpp"
#include <vector>
// select(i,j,k) -> true if (i,k) is better than (i,j)
template <typename F> std::vector<int> monotone_minima(int H, int W, const F &select) {
 std::vector<int> ret(H);
 auto rec= [&](auto &rec, int h1, int h2, int w1, int w2) -> void {
  if (h1 == h2) return;
  int h= (h1 + h2) / 2, best_w= w1;
  for (int w= w1 + 1; w < w2; ++w)
   if (select(h, best_w, w)) best_w= w;
  ret[h]= best_w, rec(rec, h1, h, w1, best_w + 1), rec(rec, h + 1, h2, best_w, w2);
 };
 return rec(rec, 0, H, 0, W), ret;
}
#line 6 "test/yosupo/min_plus_convolution_convex_arbitrary.monotone_minima.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, M;
 cin >> N >> M;
 long long a[N], b[M];
 for (int i= 0; i < N; ++i) cin >> a[i];
 for (int j= 0; j < M; ++j) cin >> b[j];
 auto select= [&](int i, int j, int k) {
  if (i < k) return false;
  if (i - j >= N) return true;
  return a[i - j] + b[j] >= a[i - k] + b[k];
 };
 auto r= monotone_minima(N + M - 1, M, select);
 for (int i= 0; i < N + M - 1; ++i) cout << a[i - r[i]] + b[r[i]] << " \n"[i == N + M - 2];
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	example_00	AC	5 ms	4 MB
g++-13	hack_00	AC	4 ms	4 MB
g++-13	large_small_00	AC	70 ms	12 MB
g++-13	large_small_01	AC	69 ms	11 MB
g++-13	large_small_02	AC	72 ms	12 MB
g++-13	large_small_03	AC	73 ms	12 MB
g++-13	max_random_00	AC	168 ms	20 MB
g++-13	max_random_01	AC	168 ms	20 MB
g++-13	max_random_02	AC	157 ms	20 MB
g++-13	med_random_00	AC	5 ms	4 MB
g++-13	med_random_01	AC	4 ms	4 MB
g++-13	med_random_02	AC	4 ms	4 MB
g++-13	monotone_00	AC	171 ms	20 MB
g++-13	monotone_01	AC	153 ms	20 MB
g++-13	monotone_02	AC	159 ms	20 MB
g++-13	monotone_03	AC	158 ms	20 MB
g++-13	near_power_of_2_00	AC	82 ms	11 MB
g++-13	near_power_of_2_01	AC	89 ms	12 MB
g++-13	near_power_of_2_02	AC	81 ms	12 MB
g++-13	near_power_of_2_03	AC	82 ms	11 MB
g++-13	near_power_of_2_04	AC	81 ms	12 MB
g++-13	near_power_of_2_05	AC	82 ms	12 MB
g++-13	near_power_of_2_06	AC	82 ms	12 MB
g++-13	near_power_of_2_07	AC	81 ms	12 MB
g++-13	near_power_of_2_08	AC	82 ms	11 MB
g++-13	only_first_small_00	AC	163 ms	20 MB
g++-13	only_first_small_01	AC	154 ms	20 MB
g++-13	random_00	AC	124 ms	16 MB
g++-13	random_01	AC	132 ms	17 MB
g++-13	random_02	AC	79 ms	10 MB
g++-13	small_00	AC	5 ms	4 MB
g++-13	small_01	AC	4 ms	4 MB
g++-13	small_02	AC	4 ms	4 MB
g++-13	small_03	AC	4 ms	4 MB
g++-13	small_04	AC	4 ms	4 MB
g++-13	small_05	AC	4 ms	4 MB
g++-13	small_06	AC	4 ms	4 MB
g++-13	small_07	AC	4 ms	4 MB
g++-13	small_08	AC	4 ms	4 MB
g++-13	small_slopes_00	AC	157 ms	20 MB
g++-13	small_slopes_01	AC	171 ms	20 MB
clang++-18	example_00	AC	5 ms	4 MB
clang++-18	hack_00	AC	4 ms	4 MB
clang++-18	large_small_00	AC	61 ms	11 MB
clang++-18	large_small_01	AC	62 ms	12 MB
clang++-18	large_small_02	AC	82 ms	12 MB
clang++-18	large_small_03	AC	82 ms	11 MB
clang++-18	max_random_00	AC	129 ms	20 MB
clang++-18	max_random_01	AC	133 ms	20 MB
clang++-18	max_random_02	AC	130 ms	20 MB
clang++-18	med_random_00	AC	5 ms	4 MB
clang++-18	med_random_01	AC	4 ms	4 MB
clang++-18	med_random_02	AC	4 ms	4 MB
clang++-18	monotone_00	AC	130 ms	20 MB
clang++-18	monotone_01	AC	126 ms	20 MB
clang++-18	monotone_02	AC	132 ms	20 MB
clang++-18	monotone_03	AC	148 ms	20 MB
clang++-18	near_power_of_2_00	AC	72 ms	11 MB
clang++-18	near_power_of_2_01	AC	67 ms	12 MB
clang++-18	near_power_of_2_02	AC	78 ms	11 MB
clang++-18	near_power_of_2_03	AC	68 ms	12 MB
clang++-18	near_power_of_2_04	AC	67 ms	12 MB
clang++-18	near_power_of_2_05	AC	68 ms	11 MB
clang++-18	near_power_of_2_06	AC	71 ms	12 MB
clang++-18	near_power_of_2_07	AC	69 ms	12 MB
clang++-18	near_power_of_2_08	AC	70 ms	12 MB
clang++-18	only_first_small_00	AC	129 ms	20 MB
clang++-18	only_first_small_01	AC	132 ms	20 MB
clang++-18	random_00	AC	101 ms	16 MB
clang++-18	random_01	AC	109 ms	17 MB
clang++-18	random_02	AC	61 ms	10 MB
clang++-18	small_00	AC	5 ms	4 MB
clang++-18	small_01	AC	4 ms	4 MB
clang++-18	small_02	AC	4 ms	4 MB
clang++-18	small_03	AC	4 ms	4 MB
clang++-18	small_04	AC	4 ms	4 MB
clang++-18	small_05	AC	4 ms	4 MB
clang++-18	small_06	AC	4 ms	4 MB
clang++-18	small_07	AC	4 ms	4 MB
clang++-18	small_08	AC	4 ms	4 MB
clang++-18	small_slopes_00	AC	145 ms	20 MB
clang++-18	small_slopes_01	AC	137 ms	20 MB

Back to top page