src/conv/min_plus/cv/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../opt/smawk/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | //! assume a is convex, aka. $a_{i-1} - a_{i-2} \leq a_i - a_{i-1}$ | ||
| 8 | //! assume b is arbitrary, aka. $b_i = b_j \iff i = j$ | ||
| 9 | template <class T> | ||
| 10 | 41 | CEXP vec<T> conv_minplus_cv(vec<T> CR a, vec<T> CR b) NE { | |
| 11 | 41 | cu32 n = (u32)a.size(), m = (u32)b.size(); | |
| 12 | 41 | cvecu argmin = smawk( | |
| 13 | 41 | n + m - 1, | |
| 14 | m, | ||
| 15 | 41 | [&](u32 k, u32 j1, u32 j2) NE -> bool { | |
| 16 | 203543567 | ci32 i1 = (i32)k - (i32)j1, i2 = (i32)k - (i32)j2; | |
| 17 |
2/2✓ Branch 0 taken 15766154 times.
✓ Branch 1 taken 187777413 times.
|
203543567 | if (i2 < 0) return true; |
| 18 |
2/2✓ Branch 0 taken 15575206 times.
✓ Branch 1 taken 172202207 times.
|
187777413 | if (i1 >= (i32)n) return false; |
| 19 | 172202207 | return a[(u32)i1] + b[j1] < a[(u32)i2] + b[j2]; | |
| 20 | }); | ||
| 21 | 41 | vec<T> c(n + m - 1); | |
| 22 |
2/2✓ Branch 5 taken 20464989 times.
✓ Branch 6 taken 41 times.
|
20465030 | flt_ (u32, k, 0, n + m - 1) c[k] = a[k - argmin[k]] + b[argmin[k]]; |
| 23 | 41 | return c; | |
| 24 | 41 | } | |
| 25 | |||
| 26 | } // namespace tifa_libs | ||
| 27 |