
def 		UpperCamelCase						(   )		->						list[list[int]]:


  '''simple docstring'''






  return [list(range(10_00 - i			,			-10_00 - i			,			-1 ) ) for i in range(10_00 )]


lowerCamelCase__     :		str        = generate_large_matrix()
lowerCamelCase__     :		Dict        = (
    [[4, 3, 2, -1], [3, 2, 1, -1], [1, 1, -1, -2], [-1, -1, -2, -3]],
    [[3, 2], [1, 0]],
    [[7, 7, 6]],
    [[7, 7, 6], [-1, -2, -3]],
    grid,
)

def 		UpperCamelCase						(   lowercase_ )		->						None:


  '''simple docstring'''






  assert all(row == sorted(lowercase_			,			reverse=lowercase_ ) for row in grid )
  assert all(list(lowercase_ ) == sorted(lowercase_			,			reverse=lowercase_ ) for col in zip(*lowercase_ ) )

def 		UpperCamelCase						(   lowercase_ )		->						int:


  '''simple docstring'''






  lowercase__	: Optional[int]     		=   0
  lowercase__	: Optional[int]     		=   len(lowercase_ ) - 1

  # Edge cases such as no values or all numbers are negative.
  if not array or array[0] < 0:
    return 0

  while right + 1 > left:
    lowercase__	: Optional[int]     		=   (left + right) // 2
    lowercase__	: Union[str, Any]     		=   array[mid]

    # Num must be negative and the index must be greater than or equal to 0.
    if num < 0 and array[mid - 1] >= 0:
      return mid

    if num >= 0:
      lowercase__	: int     		=   mid + 1
    else:
      lowercase__	: Any     		=   mid - 1
    # No negative numbers so return the last index of the array + 1 which is the length.
  return len(lowercase_ )

def 		UpperCamelCase						(   lowercase_ )		->						int:


  '''simple docstring'''






  lowercase__	: List[Any]     		=   0
  lowercase__	: int     		=   len(grid[0] )

  for i in range(len(lowercase_ ) ):
    lowercase__	: Tuple     		=   find_negative_index(grid[i][:bound] )
    total += bound
  return (len(lowercase_ ) * len(grid[0] )) - total

def 		UpperCamelCase						(   lowercase_ )		->						int:


  '''simple docstring'''






  return len([number for row in grid for number in row if number < 0] )

def 		UpperCamelCase						(   lowercase_ )		->						int:


  '''simple docstring'''






  lowercase__	: Tuple     		=   0
  for row in grid:
    for i, number in enumerate(lowercase_ ):
      if number < 0:
        total += len(lowercase_ ) - i
        break
  return total

def 		UpperCamelCase						(   )		->						None:


  '''simple docstring'''






  from timeit import timeit

  print("""Running benchmarks""" )
  lowercase__	: Optional[int]     		=   (
      """from __main__ import count_negatives_binary_search, """
      """count_negatives_brute_force, count_negatives_brute_force_with_break, grid"""
  )
  for func in (
      "count_negatives_binary_search",  # took 0.7727 seconds
      "count_negatives_brute_force_with_break",  # took 4.6505 seconds
      "count_negatives_brute_force",  # took 12.8160 seconds
  ):
    lowercase__	: Tuple     		=   timeit(F'{func}(grid=grid)'			,			setup=lowercase_			,			number=5_00 )
    print(F'{func}() took {time:0.4f} seconds' )


if __name__ == "__main__":
     import doctest

     doctest.testmod()
     benchmark()








def 		UpperCamelCase						(   lowercase_			,			lowercase_			,			lowercase_			,			lowercase_ )		->						List[str]:


  '''simple docstring'''






  global f  # a global dp table for knapsack
  if f[i][j] < 0:
    if j < wt[i - 1]:
      lowercase__	: str     		=   mf_knapsack(i - 1			,			lowercase_			,			lowercase_			,			lowercase_ )
    else:
      lowercase__	: List[str]     		=   max(
          mf_knapsack(i - 1			,			lowercase_			,			lowercase_			,			lowercase_ )			,			mf_knapsack(i - 1			,			lowercase_			,			lowercase_			,			j - wt[i - 1] ) + val[i - 1]			,			)
    lowercase__	: List[Any]     		=   val
  return f[i][j]

def 		UpperCamelCase						(   lowercase_			,			lowercase_			,			lowercase_			,			lowercase_ )		->						str:


  '''simple docstring'''






  lowercase__	: Any     		=   [[0] * (w + 1) for _ in range(n + 1 )]

  for i in range(1			,			n + 1 ):
    for w_ in range(1			,			w + 1 ):
      if wt[i - 1] <= w_:
        lowercase__	: List[Any]     		=   max(val[i - 1] + dp[i - 1][w_ - wt[i - 1]]			,			dp[i - 1][w_] )
      else:
        lowercase__	: Tuple     		=   dp[i - 1][w_]

  return dp[n][w_], dp

def 		UpperCamelCase						(   lowercase_			,			lowercase_			,			lowercase_ )		->						Optional[Any]:


  '''simple docstring'''






  if not (isinstance(lowercase_			,			(list, tuple) ) and isinstance(lowercase_			,			(list, tuple) )):
    raise ValueError(
        """Both the weights and values vectors must be either lists or tuples""" )

  lowercase__	: str     		=   len(lowercase_ )
  if num_items != len(lowercase_ ):
    lowercase__	: Optional[int]     		=   (
        """The number of weights must be the same as the number of values.\n"""
        F'But got {num_items} weights and {len(lowercase_ )} values'
    )
    raise ValueError(lowercase_ )
  for i in range(lowercase_ ):
    if not isinstance(wt[i]			,			lowercase_ ):
      lowercase__	: int     		=   (
          """All weights must be integers but got weight of """
          F'type {type(wt[i] )} at index {i}'
      )
      raise TypeError(lowercase_ )

  lowercase__		,     lowercase__	: Tuple     		=   knapsack(lowercase_			,			lowercase_			,			lowercase_			,			lowercase_ )
  lowercase__	: set     		=   set()
  _construct_solution(lowercase_			,			lowercase_			,			lowercase_			,			lowercase_			,			lowercase_ )

  return optimal_val, example_optional_set

def 		UpperCamelCase						(   lowercase_			,			lowercase_			,			lowercase_			,			lowercase_			,			lowercase_ )		->						Any:


  '''simple docstring'''






  if i > 0 and j > 0:
    if dp[i - 1][j] == dp[i][j]:
      _construct_solution(lowercase_			,			lowercase_			,			i - 1			,			lowercase_			,			lowercase_ )
    else:
      optimal_set.add(lowercase_ )
      _construct_solution(lowercase_			,			lowercase_			,			i - 1			,			j - wt[i - 1]			,			lowercase_ )


if __name__ == "__main__":
     lowerCamelCase__     :		Dict        = [3, 2, 4, 4]
     lowerCamelCase__     :		List[Any]        = [4, 3, 2, 3]
     lowerCamelCase__     :		Optional[int]        = 4
     lowerCamelCase__     :		Dict        = 6
     lowerCamelCase__     :		Optional[int]        = [[0] * (w + 1)] + [[0] + [-1] * (w + 1) for _ in range(n + 1)]
     lowerCamelCase__   ,    lowerCamelCase__     :		int        = knapsack(w, wt, val, n)
     print(optimal_solution)
     print(mf_knapsack(n, wt, val, w))  # switched the n and w

     # testing the dynamic programming problem with example
     # the optimal subset for the above example are items 3 and 4
     lowerCamelCase__   ,    lowerCamelCase__     :		Optional[int]        = knapsack_with_example_solution(w, wt, val)
     assert optimal_solution == 8
     assert optimal_subset == {3, 4}
     print("""optimal_value = """, optimal_solution)
     print("""An optimal subset corresponding to the optimal value""", optimal_subset)






