src/opt/larsch/d2/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../util/traits/math/lib.hpp" | ||
| 4 | #include "../../smawk/lib.hpp" | ||
| 5 | |||
| 6 | namespace tifa_libs { | ||
| 7 | |||
| 8 | template <arithm_c T, class Func> | ||
| 9 | requires requires(Func f, u32 x, u32 y) { {f(x,y)}->std::same_as<T>; } | ||
| 10 | 26 | CEXP vec<T> larsch_2d(u32 n, Func&& w, T inf = inf_v<T>) NE { | |
| 11 | using W = to_bigger_t<T>; | ||
| 12 | 52 | vec<W> dp(n + 1, inf_v<W>); | |
| 13 | 26 | vec<T> ans(n + 1, inf); | |
| 14 | 26 | dp[0] = 0; | |
| 15 |
2/2✓ Branch 0 taken 1309128017 times.
✓ Branch 1 taken 365192279 times.
|
1674320296 | auto f = [&](u32 j, u32 i) -> W { retif_((i < j), dp[i] + w(i, j), inf_v<W>); }; |
| 16 |
2/2✓ Branch 0 taken 35199 times.
✓ Branch 1 taken 26 times.
|
35225 | flt_ (u32, d, 1, n) { |
| 17 | 837195347 | auto argmin = smawk(n + 1, n + 1, [&](u32 i, u32 j, u32 k) { return f(i, j) <= f(i, k); }); | |
| 18 |
2/2✓ Branch 5 taken 37373419 times.
✓ Branch 6 taken 35199 times.
|
37408618 | for (u32 i = n; i >= d; --i) dp[i] = dp[argmin[i]] + w(argmin[i], i); |
| 19 | 35199 | ans[d] = (T)dp[n]; | |
| 20 | } | ||
| 21 | 26 | return ans; | |
| 22 | 26 | }; | |
| 23 | |||
| 24 | } // namespace tifa_libs | ||
| 25 |