src/opt/knapsack/bin/lib.hpp - GCC Code Coverage Report

Directory:	./
Coverage:	low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%

	Coverage	Exec / Excl / Total
Lines:	97.6%	80 / 0 / 82
Functions:	100.0%	6 / 0 / 6
Branches:	85.5%	65 / 0 / 76

    src/opt/knapsack/bin/lib.hpp
    
        Line
        Branch
        Exec
        Source
      
        #pragma once
      
        #include "../../../util/alias/others/lib.hpp"
      
        #include "../../../util/traits/math/lib.hpp"
      
        namespace tifa_libs {
      
        //@param a a[i]={value, weight}
      
        //@param W max weight
      
        //@return max total value while total weight <= W
      
        template <int_c T>
      
        100
        CEXP T knapsack_01(vecpt<T> CR a, T W) NE {
      
        200
          const T vs = [k = std::views::keys(a)] { return std::reduce(begin(k), end(k), T{}); }();
      
        100
          const T _1 = W, _2 = vs,
      
          3/4tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda()#1}::operator()() const:
✓ Branch 1 taken 40 times.
✓ Branch 2 taken 28 times.
tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda()#1}::operator()() const:
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.

        100
                  _3 = T(a.size() >= 100 ? inf_v<T> : (T)min((u64)inf_v<T>, 1_u64 << ((a.size() + 1) / 2))),
      
        100
                  _min = min({_1, _2, _3});
      
          4/8tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda()#1}::operator()() const:
✓ Branch 1 taken 68 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 68 times.
✗ Branch 5 not taken.
tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda()#1}::operator()() const:
✓ Branch 1 taken 32 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 32 times.
✗ Branch 5 not taken.

        100
          assert(0_isz <= (isz)_min && (usz)_min * a.size() < (usz)1e9);
      
          4/4tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda()#1}::operator()() const:
✓ Branch 0 taken 41 times.
✓ Branch 1 taken 27 times.
tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda()#1}::operator()() const:
✓ Branch 0 taken 13 times.
✓ Branch 1 taken 19 times.

        100
          if (_min == _1) {
      
        54
            vec<T> dp(W + 1);
      
          4/4tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda()#1}::operator()() const:
✓ Branch 7 taken 2190 times.
✓ Branch 8 taken 41 times.
tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda()#1}::operator()() const:
✓ Branch 7 taken 324 times.
✓ Branch 8 taken 13 times.

        2568
            for (auto [s, t] : a)
      
          4/4tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda()#1}::operator()() const:
✓ Branch 4 taken 7796505 times.
✓ Branch 5 taken 2190 times.
tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda()#1}::operator()() const:
✓ Branch 4 taken 200235 times.
✓ Branch 5 taken 324 times.

        7999254
              for (u32 j = u32(W - t); (i32)j >= 0; --j) dp[j + t] = max(dp[j + t], dp[j] + s);
      
        54
            return max(dp);
      
          4/4tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda()#1}::operator()() const:
✓ Branch 1 taken 18 times.
✓ Branch 2 taken 9 times.
tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda()#1}::operator()() const:
✓ Branch 1 taken 2 times.
✓ Branch 2 taken 17 times.

        100
          } else if (const T inf = to_uint_t<T>(-1) / 2 - 1; _min == _2) {
      
        20
            vec<T> dp(vs + 1, inf);
      
        20
            dp[0] = 0;
      
          4/4tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda()#1}::operator()() const:
✓ Branch 7 taken 1255 times.
✓ Branch 8 taken 18 times.
tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda()#1}::operator()() const:
✓ Branch 7 taken 57 times.
✓ Branch 8 taken 2 times.

        1332
            for (auto [s, t] : a)
      
          4/4tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda()#1}::operator()() const:
✓ Branch 4 taken 5342558 times.
✓ Branch 5 taken 1255 times.
tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda()#1}::operator()() const:
✓ Branch 4 taken 2815 times.
✓ Branch 5 taken 57 times.

        5346685
              for (u32 j = u32(vs - s); (i32)j >= 0; --j) dp[j + s] = min(dp[j + s], dp[j] + t);
      
        20
            T ans = 0;
      
          4/4tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda()#1}::operator()() const:
✓ Branch 0 taken 57530 times.
✓ Branch 1 taken 18 times.
tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda()#1}::operator()() const:
✓ Branch 0 taken 102 times.
✓ Branch 1 taken 2 times.

        57652
            flt_ (T, i, 0, T(vs + 1))
      
          3/4tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda()#1}::operator()() const:
✓ Branch 1 taken 20516 times.
✓ Branch 2 taken 37014 times.
tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda()#1}::operator()() const:
✓ Branch 1 taken 102 times.
✗ Branch 2 not taken.

        57632
              if (dp[i] <= W) ans = max(ans, i);
      
        20
            return ans;
      
        20
          } else {
      
        52
            auto f = [&](u32 l, u32 r) {
      
          2/4tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda(unsigned int, unsigned int)#1}::operator()(unsigned int, unsigned int) const:
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda(unsigned int, unsigned int)#1}::operator()(unsigned int, unsigned int) const:
✓ Branch 1 taken 34 times.
✗ Branch 2 not taken.

        52
              vecpt<T> res(1 << (r - l));
      
        52
              res[0] = {0, 0};
      
          4/4tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda(unsigned int, unsigned int)#1}::operator()(unsigned int, unsigned int) const:
✓ Branch 0 taken 73 times.
✓ Branch 1 taken 18 times.
tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda(unsigned int, unsigned int)#1}::operator()(unsigned int, unsigned int) const:
✓ Branch 0 taken 268 times.
✓ Branch 1 taken 34 times.

        393
              flt_ (u32, i, 0, r - l)
      
          4/4tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda(unsigned int, unsigned int)#1}::operator()(unsigned int, unsigned int) const:
✓ Branch 0 taken 14421 times.
✓ Branch 1 taken 73 times.
tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda(unsigned int, unsigned int)#1}::operator()(unsigned int, unsigned int) const:
✓ Branch 0 taken 4333070 times.
✓ Branch 1 taken 268 times.

        4347832
                flt_ (u32, j, 0, 1 << i) {
      
        4347491
                  auto&& [v, w] = a[l + i];
      
        4347491
                  res[je + j] = {res[j].first + w, res[j].second + v};
      
                }
      
          2/4tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda(unsigned int, unsigned int)#1}::operator()(unsigned int, unsigned int) const:
✓ Branch 1 taken 18 times.
✗ Branch 2 not taken.
tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda(unsigned int, unsigned int)#1}::operator()(unsigned int, unsigned int) const:
✓ Branch 1 taken 34 times.
✗ Branch 2 not taken.

        52
              sort(res);
      
          4/4tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda(unsigned int, unsigned int)#1}::operator()(unsigned int, unsigned int) const:
✓ Branch 5 taken 14421 times.
✓ Branch 6 taken 18 times.
tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda(unsigned int, unsigned int)#1}::operator()(unsigned int, unsigned int) const:
✓ Branch 5 taken 4333070 times.
✓ Branch 6 taken 34 times.

        4347543
              flt_ (u32, i, 1, (u32)res.size()) res[i].second = max(res[i].second, res[i - 1].second);
      
        52
              return res;
      
        ✗
            };
      
        26
            auto l = f(0, (u32)a.size() / 2), r = f((u32)a.size() / 2, (u32)a.size());
      
        26
            reverse(l), r.emplace_back(inf, inf);
      
        26
            T ans = 0;
      
        26
            u32 id = -1_u32;
      
          4/4tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda(unsigned int, unsigned int)#1}::operator()(unsigned int, unsigned int) const:
✓ Branch 7 taken 5169 times.
✓ Branch 8 taken 9 times.
tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda(unsigned int, unsigned int)#1}::operator()(unsigned int, unsigned int) const:
✓ Branch 7 taken 2143466 times.
✓ Branch 8 taken 17 times.

        2148661
            for (auto& [t, s] : l) {
      
          4/4tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda(unsigned int, unsigned int)#1}::operator()(unsigned int, unsigned int) const:
✓ Branch 1 taken 9270 times.
✓ Branch 2 taken 5169 times.
tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda(unsigned int, unsigned int)#1}::operator()(unsigned int, unsigned int) const:
✓ Branch 1 taken 1757256 times.
✓ Branch 2 taken 2143466 times.

        3915161
              while (t + r[id + 1].first <= W) ++id;
      
          3/4tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda(unsigned int, unsigned int)#1}::operator()(unsigned int, unsigned int) const:
✓ Branch 0 taken 5169 times.
✗ Branch 1 not taken.
tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda(unsigned int, unsigned int)#1}::operator()(unsigned int, unsigned int) const:
✓ Branch 0 taken 1711263 times.
✓ Branch 1 taken 432203 times.

        2148635
              if (~id) ans = max(ans, s + r[id].second);
      
            }
      
        26
            return ans;
      
        26
          }
      
        }
      
        }  // namespace tifa_libs

Line	Branch	Exec	Source
1			#pragma once
2
3			#include "../../../util/alias/others/lib.hpp"
4			#include "../../../util/traits/math/lib.hpp"
5
6			namespace tifa_libs {
7
8			//@param a a[i]={value, weight}
9			//@param W max weight
10			//@return max total value while total weight <= W
11			template <int_c T>
12		100	CEXP T knapsack_01(vecpt<T> CR a, T W) NE {
13		200	const T vs = [k = std::views::keys(a)] { return std::reduce(begin(k), end(k), T{}); }();
14		100	const T _1 = W, _2 = vs,
15	3/4 tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda()#1}::operator()() const: ✓ Branch 1 taken 40 times. ✓ Branch 2 taken 28 times. tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda()#1}::operator()() const: ✓ Branch 1 taken 32 times. ✗ Branch 2 not taken.	100	_3 = T(a.size() >= 100 ? inf_v<T> : (T)min((u64)inf_v<T>, 1_u64 << ((a.size() + 1) / 2))),
16		100	_min = min({_1, _2, _3});
17	4/8 tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda()#1}::operator()() const: ✓ Branch 1 taken 68 times. ✗ Branch 2 not taken. ✓ Branch 4 taken 68 times. ✗ Branch 5 not taken. tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda()#1}::operator()() const: ✓ Branch 1 taken 32 times. ✗ Branch 2 not taken. ✓ Branch 4 taken 32 times. ✗ Branch 5 not taken.	100	assert(0_isz <= (isz)_min && (usz)_min * a.size() < (usz)1e9);
18	4/4 tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda()#1}::operator()() const: ✓ Branch 0 taken 41 times. ✓ Branch 1 taken 27 times. tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda()#1}::operator()() const: ✓ Branch 0 taken 13 times. ✓ Branch 1 taken 19 times.	100	if (_min == _1) {
19		54	vec<T> dp(W + 1);
20	4/4 tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda()#1}::operator()() const: ✓ Branch 7 taken 2190 times. ✓ Branch 8 taken 41 times. tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda()#1}::operator()() const: ✓ Branch 7 taken 324 times. ✓ Branch 8 taken 13 times.	2568	for (auto [s, t] : a)
21	4/4 tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda()#1}::operator()() const: ✓ Branch 4 taken 7796505 times. ✓ Branch 5 taken 2190 times. tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda()#1}::operator()() const: ✓ Branch 4 taken 200235 times. ✓ Branch 5 taken 324 times.	7999254	for (u32 j = u32(W - t); (i32)j >= 0; --j) dp[j + t] = max(dp[j + t], dp[j] + s);
22		54	return max(dp);
23	4/4 tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda()#1}::operator()() const: ✓ Branch 1 taken 18 times. ✓ Branch 2 taken 9 times. tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda()#1}::operator()() const: ✓ Branch 1 taken 2 times. ✓ Branch 2 taken 17 times.	100	} else if (const T inf = to_uint_t<T>(-1) / 2 - 1; _min == _2) {
24		20	vec<T> dp(vs + 1, inf);
25		20	dp[0] = 0;
26	4/4 tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda()#1}::operator()() const: ✓ Branch 7 taken 1255 times. ✓ Branch 8 taken 18 times. tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda()#1}::operator()() const: ✓ Branch 7 taken 57 times. ✓ Branch 8 taken 2 times.	1332	for (auto [s, t] : a)
27	4/4 tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda()#1}::operator()() const: ✓ Branch 4 taken 5342558 times. ✓ Branch 5 taken 1255 times. tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda()#1}::operator()() const: ✓ Branch 4 taken 2815 times. ✓ Branch 5 taken 57 times.	5346685	for (u32 j = u32(vs - s); (i32)j >= 0; --j) dp[j + s] = min(dp[j + s], dp[j] + t);
28		20	T ans = 0;
29	4/4 tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda()#1}::operator()() const: ✓ Branch 0 taken 57530 times. ✓ Branch 1 taken 18 times. tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda()#1}::operator()() const: ✓ Branch 0 taken 102 times. ✓ Branch 1 taken 2 times.	57652	flt_ (T, i, 0, T(vs + 1))
30	3/4 tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda()#1}::operator()() const: ✓ Branch 1 taken 20516 times. ✓ Branch 2 taken 37014 times. tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda()#1}::operator()() const: ✓ Branch 1 taken 102 times. ✗ Branch 2 not taken.	57632	if (dp[i] <= W) ans = max(ans, i);
31		20	return ans;
32		20	} else {
33		52	auto f = [&](u32 l, u32 r) {
34	2/4 tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda(unsigned int, unsigned int)#1}::operator()(unsigned int, unsigned int) const: ✓ Branch 1 taken 18 times. ✗ Branch 2 not taken. tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda(unsigned int, unsigned int)#1}::operator()(unsigned int, unsigned int) const: ✓ Branch 1 taken 34 times. ✗ Branch 2 not taken.	52	vecpt<T> res(1 << (r - l));
35		52	res[0] = {0, 0};
36	4/4 tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda(unsigned int, unsigned int)#1}::operator()(unsigned int, unsigned int) const: ✓ Branch 0 taken 73 times. ✓ Branch 1 taken 18 times. tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda(unsigned int, unsigned int)#1}::operator()(unsigned int, unsigned int) const: ✓ Branch 0 taken 268 times. ✓ Branch 1 taken 34 times.	393	flt_ (u32, i, 0, r - l)
37	4/4 tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda(unsigned int, unsigned int)#1}::operator()(unsigned int, unsigned int) const: ✓ Branch 0 taken 14421 times. ✓ Branch 1 taken 73 times. tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda(unsigned int, unsigned int)#1}::operator()(unsigned int, unsigned int) const: ✓ Branch 0 taken 4333070 times. ✓ Branch 1 taken 268 times.	4347832	flt_ (u32, j, 0, 1 << i) {
38		4347491	auto&& [v, w] = a[l + i];
39		4347491	res[je + j] = {res[j].first + w, res[j].second + v};
40			}
41	2/4 tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda(unsigned int, unsigned int)#1}::operator()(unsigned int, unsigned int) const: ✓ Branch 1 taken 18 times. ✗ Branch 2 not taken. tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda(unsigned int, unsigned int)#1}::operator()(unsigned int, unsigned int) const: ✓ Branch 1 taken 34 times. ✗ Branch 2 not taken.	52	sort(res);
42	4/4 tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda(unsigned int, unsigned int)#1}::operator()(unsigned int, unsigned int) const: ✓ Branch 5 taken 14421 times. ✓ Branch 6 taken 18 times. tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda(unsigned int, unsigned int)#1}::operator()(unsigned int, unsigned int) const: ✓ Branch 5 taken 4333070 times. ✓ Branch 6 taken 34 times.	4347543	flt_ (u32, i, 1, (u32)res.size()) res[i].second = max(res[i].second, res[i - 1].second);
43		52	return res;
44		✗	};
45		26	auto l = f(0, (u32)a.size() / 2), r = f((u32)a.size() / 2, (u32)a.size());
46		26	reverse(l), r.emplace_back(inf, inf);
47		26	T ans = 0;
48		26	u32 id = -1_u32;
49	4/4 tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda(unsigned int, unsigned int)#1}::operator()(unsigned int, unsigned int) const: ✓ Branch 7 taken 5169 times. ✓ Branch 8 taken 9 times. tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda(unsigned int, unsigned int)#1}::operator()(unsigned int, unsigned int) const: ✓ Branch 7 taken 2143466 times. ✓ Branch 8 taken 17 times.	2148661	for (auto& [t, s] : l) {
50	4/4 tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda(unsigned int, unsigned int)#1}::operator()(unsigned int, unsigned int) const: ✓ Branch 1 taken 9270 times. ✓ Branch 2 taken 5169 times. tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda(unsigned int, unsigned int)#1}::operator()(unsigned int, unsigned int) const: ✓ Branch 1 taken 1757256 times. ✓ Branch 2 taken 2143466 times.	3915161	while (t + r[id + 1].first <= W) ++id;
51	3/4 tifa_libs::knapsack_01<unsigned int>(std::vector<std::pair<unsigned int, unsigned int>, std::allocator<std::pair<unsigned int, unsigned int> > > const&, unsigned int)::{lambda(unsigned int, unsigned int)#1}::operator()(unsigned int, unsigned int) const: ✓ Branch 0 taken 5169 times. ✗ Branch 1 not taken. tifa_libs::knapsack_01<unsigned long>(std::vector<std::pair<unsigned long, unsigned long>, std::allocator<std::pair<unsigned long, unsigned long> > > const&, unsigned long)::{lambda(unsigned int, unsigned int)#1}::operator()(unsigned int, unsigned int) const: ✓ Branch 0 taken 1711263 times. ✓ Branch 1 taken 432203 times.	2148635	if (~id) ans = max(ans, s + r[id].second);
52			}
53		26	return ans;
54		26	}
55			}
56
57			} // namespace tifa_libs
58