A conveyor belt has packages that must be shipped from one port to another within D days.
The i-th package on the conveyor belt has a weight of weights[i].  Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.
Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within D days.
 
Example 1:
Input: weights = [1,2,3,4,5,6,7,8,9,10], D = 5
Output: 15
Explanation: 
A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10

Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed. 

Example 2:
Input: weights = [3,2,2,4,1,4], D = 3
Output: 6
Explanation: 
A ship capacity of 6 is the minimum to ship all the packages in 3 days like this:
1st day: 3, 2
2nd day: 2, 4
3rd day: 1, 4

Example 3:
Input: weights = [1,2,3,1,1], D = 4
Output: 3
Explanation: 
1st day: 1
2nd day: 2
3rd day: 3
4th day: 1, 1

 
Constraints:

1 <= D <= weights.length <= 50000
1 <= weights[i] <= 500

Source: leetcode | Difficulty: MEDIUM
Tags: Sorting

Data structures

Starter code: class Solution:
    def shipWithinDays(self, weights: List[int], D: int) -> int:
        

Solutions:
class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		left = max(weights)
		right = left * len(weights) // D
		while left < right:
			mid = left + (right - left) // 2
			c = 0
			d = 1
			for w in weights:
				if c + w <= mid:
					c += w
				else:
					d += 1
					c = w
			if d > D:
				left = mid + 1
			else:
				right = mid
		return left


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def checkCapacity(cap: int, weights: List[int], D: int):
			val = 0
			res = 1
			for w in weights:
				val += w
				if val > cap:
					res += 1
					val = w
			return res <= D
		low = max(weights)
		high = min(sum(weights), low * len(weights) // D)
		while low < high:
			mid = (low + high) // 2
			if checkCapacity(mid, weights, D):
				high = mid
			else:
				low = mid + 1
		return high


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def canShip(capacity: int) -> bool:
			nonlocal D
			count = 1
			curcap = 0
			for w in weights:
				if curcap + w <= capacity:
					curcap += w
				else:
					count += 1
					curcap = w
			return count <= D
		max_weight = max(weights)
		lo = sum(weights) // D
		hi = max_weight * (len(weights) // D + 1)
		while lo < hi:
			mid = (lo + hi) // 2
			if mid < max_weight or not canShip(mid):
				lo = mid + 1
			else:
				hi = mid
		return lo


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		start = max(weights)
		end = sum(weights)
		while start < end:
			mid = start + (end - start) // 2
			print(mid)
			counter = 0
			summation = 0
			for i in weights:
				if summation + i == mid:
					counter += 1
					summation = 0
				elif summation + i > mid:
					counter += 1
					summation = i
				elif summation < mid:
					summation += i
			counter += 1
			print(counter)
			if counter > D:
				start = mid + 1
			else:
				end = mid
		return start


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		lo = 0
		hi = 0
		for i in range(len(weights)):
			lo = max(lo, weights[i])
			hi = hi + weights[i]
		optimalcapacity = hi + 1
		while lo <= hi:
			days = 1
			capacity = 0
			mid = lo + (hi - lo) // 2
			for i in range(len(weights)):
				if weights[i] + capacity > mid:
					days = days + 1
					capacity = weights[i]
				else:
					capacity += weights[i]
			if days <= D:
				hi = mid - 1
				optimalcapacity = min(optimalcapacity, mid)
			else:
				lo = mid + 1
		return optimalcapacity


def find(w, m, d, l):
	s = 0
	c = 1
	for i in range(l):
		s += w[i]
		if s > m:
			s = w[i]
			c += 1
		if c > d:
			return False
	return True

class Solution:

	def shipWithinDays(self, w: List[int], D: int) -> int:
		l = len(w)
		s = max(w)
		e = sum(w)
		m = s + (e - s) // 2
		p = 0
		while s <= e:
			a = find(w, m, D, l)
			if a == True:
				p = m
				e = m - 1
				m = s + (e - s) // 2
			else:
				s = m + 1
				m = s + (e - s) // 2
		return p


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		left = max(weights)
		right = sum(weights)
		while left <= right:
			(mid, days_needed, cur) = (int((left + right) / 2), 1, 0)
			for w in weights:
				if cur + w > mid:
					days_needed += 1
					cur = 0
				cur += w
			if days_needed > D:
				left = mid + 1
			else:
				right = mid - 1
		return left


def possible(weights, cap, D):
	if cap <= 0:
		return False
	c = 1
	cur = 0
	for w in weights:
		if cur + w <= cap:
			cur += w
		elif w <= cap:
			c += 1
			cur = w
		else:
			return False
	print(c, cap)
	return c <= D

class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		(hi, lo) = (sum(weights), max(weights))
		mid = (hi + lo) // 2
		while lo <= hi:
			print(lo, hi, mid)
			p = possible(weights, mid, D)
			if p and (not possible(weights, mid - 1, D)):
				return mid
			elif not p:
				lo = mid + 1
			else:
				hi = mid
			mid = (hi + lo) // 2
		return -1


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		left = max(weights)

		def possible(c):
			ship = 1
			cargo = 0
			for i in range(len(weights)):
				if ship > D:
					return False
				if cargo + weights[i] > c:
					ship += 1
					cargo = weights[i]
				else:
					cargo += weights[i]
			return ship <= D
		right = sum(weights)
		while left <= right:
			mid = floor((left + right) / 2)
			if possible(mid):
				if left == mid:
					break
				right = mid
			else:
				left = mid + 1
		print(left, right, mid)
		return mid


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def test_ship_weights(capacity):
			dq = collections.deque(weights)
			for day in range(D):
				daily_capacity = capacity
				while dq and dq[0] <= daily_capacity:
					daily_capacity -= dq.popleft()
			if dq:
				return False
			else:
				return True
		(l, r) = (0, sum(weights))
		while l < r:
			m = (l + r) // 2 + 1
			if test_ship_weights(m):
				r = m - 1
			else:
				l = m + 1
		if test_ship_weights(l):
			return l
		if test_ship_weights(r):
			return r
		if test_ship_weights(m):
			return m
		else:
			return r + 1
		return l


class Solution:

	def isPossible(self, ship_weight: int, d: int) -> bool:
		i = 0
		ships = 0
		curr_w = 0
		while i < len(self.weights):
			if ship_weight - curr_w < self.weights[i]:
				curr_w = 0
				ships += 1
				if ship_weight < self.weights[i] or ships >= d:
					return False
			curr_w += self.weights[i]
			i += 1
		return True

	def shipWithinDays(self, weights: List[int], d: int) -> int:
		self.weights = weights
		min_w = math.ceil(sum(weights) / d)
		max_w = max(weights) * math.ceil(len(weights) / d) + 1
		while True:
			mid_w = min_w + (max_w - min_w) // 2
			if self.isPossible(mid_w, d):
				if not self.isPossible(mid_w - 1, d):
					return mid_w
				max_w = mid_w
			else:
				min_w = mid_w
		return 0


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		average = sum(weights) // len(weights)
		min_capacity = max(max(weights), average)
		min_w = min_capacity
		max_w = min_w * 2
		while not enought_capacity(max_w, weights, D):
			min_w = max_w
			max_w = max_w * 2
		while True:
			mid = min_w + (max_w - min_w) // 2
			if enought_capacity(mid, weights, D):
				if mid == min_w or mid == max_w:
					return mid
				max_w = mid
			else:
				min_w = mid + 1

def enought_capacity(capacity: int, weights: List[int], D: int):
	remain_ships = D - 1
	sum_weight = 0
	for pck_weight in weights:
		sum_weight += pck_weight
		if sum_weight > capacity:
			remain_ships -= 1
			sum_weight = pck_weight
	if remain_ships >= 0:
		return True
	return False


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		left = max(weights)
		right = sum(weights)

		def counter(limit):
			curr = 0
			count = 0
			for w in weights:
				if curr + w == limit:
					count += 1
					curr = 0
				elif curr + w > limit:
					count += 1
					curr = w
				else:
					curr += w
			return count if curr == 0 else count + 1
		res = right
		while left <= right:
			mid = (left + right) // 2
			val = counter(mid)
			if val <= D:
				res = min(res, mid)
				right = mid - 1
			else:
				left = mid + 1
		return res


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		lower = min(weights)
		upper = sum(weights)
		while lower < upper:
			mid = (lower + upper) // 2
			if self.check(weights, D, mid):
				upper = mid
			else:
				lower = mid + 1
		return lower

	def check(self, weights, D, cap):
		s = weights[0]
		ct = 1
		if s > cap:
			return False
		for x in weights[1:]:
			if x > cap:
				return False
			if s + x <= cap:
				s += x
			else:
				s = x
				ct += 1
		return ct <= D


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def isvalid(mid):
			total = 0
			package = 1
			for weight in weights:
				if weight > mid:
					return False
				total += weight
				if total > mid:
					package += 1
					total = weight
			return package <= D

		def binsearch(low, high):
			while low < high:
				mid = low + (high - low) // 2
				print(isvalid(mid), mid)
				if not isvalid(mid):
					low = mid + 1
				else:
					high = mid
			return low
		return binsearch(0, sum(weights))


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		(left, right) = (max(weights), sum(weights))

		def condition(m):
			days = 0
			cap = m
			n = len(weights)
			i = 0
			while i < n:
				w = weights[i]
				if m - w >= 0:
					m -= w
					i += 1
				else:
					days += 1
					m = cap - w
					i += 1
				if days > D:
					return False
			days += 1
			if days > D:
				return False
			return True
		while left < right:
			mid = left + (right - left) // 2
			if condition(mid):
				right = mid
			else:
				left = mid + 1
		return left


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def helper(c):
			s = 0
			d = 1
			for w in weights:
				s += w
				if s > c:
					d += 1
					s = w
					if d > D:
						return False
			return True
		l = max(weights)
		r = sum(weights)
		while l < r:
			m = l + (r - l) // 2
			if helper(m):
				r = m
			else:
				l = m + 1
		return l


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		(lo, hi) = (max(weights), sum(weights))
		while lo < hi:
			mid = (lo + hi) // 2
			(tot, res) = (0, 1)
			for wt in weights:
				if tot + wt > mid:
					res += 1
					tot = wt
				else:
					tot += wt
			if res <= D:
				hi = mid
			else:
				lo = mid + 1
		return lo


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		lo = max(weights)
		hi = sum(weights)

		def calculate_capacity(n):
			num_day = 1
			curr_capacity = 0
			for weight in weights:
				if curr_capacity + weight <= n:
					curr_capacity += weight
				else:
					num_day += 1
					curr_capacity = weight
			return num_day
		while lo < hi:
			mid = lo + (hi - lo) // 2
			day = calculate_capacity(mid)
			if day > D:
				lo = mid + 1
			else:
				hi = mid
		return lo


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		left = max(weights)
		right = left * len(weights) // D

		def checkShipping(cap):
			days = 1
			onboard = 0
			for (i, v) in enumerate(weights):
				if onboard + v > cap:
					days += 1
					onboard = v
				else:
					onboard += v
				if days > D:
					return False
			return True
		while left < right:
			mid = left + (right - left) // 2
			if checkShipping(mid):
				right = mid
			else:
				left = mid + 1
		return left


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		n = len(weights)

		def canShipWithCap(cap):
			d = 1
			w = 0
			for i in range(0, n):
				if weights[i] + w <= cap:
					w += weights[i]
				else:
					w = weights[i]
					d += 1
					if d > D:
						return False
			return True
		high = sum(weights)
		low = max(weights)
		while low < high:
			mid = low + (high - low) // 2
			if canShipWithCap(mid):
				high = mid
			else:
				low = mid + 1
		return low


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		if D == 1:
			return sum(weights)
		start = max(max(weights), -(-sum(weights) // D))
		end = sum(weights)
		n = len(weights)

		def validate(x):
			count = 0
			i = 0
			cur = 0
			while count < D:
				while i < n and cur <= x:
					cur += weights[i]
					i += 1
				if i == n and cur <= x:
					return True
				cur = weights[i - 1]
				count += 1
			return False
		while start < end:
			m = (start + end) // 2
			if validate(m):
				end = m
			else:
				start = m + 1
		return start


from collections import defaultdict

class Solution:

	def canShipWithinDays(self, weights: List[int], D: int, maxWeight: int) -> bool:
		if max(weights) > maxWeight:
			return False
		shipmentweights = [0]
		for w in weights:
			if shipmentweights[-1] + w <= maxWeight:
				shipmentweights[-1] += w
			else:
				shipmentweights.append(w)
		return len(shipmentweights) <= D

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		maxweight = sum(weights)
		minweight = max(weights)
		while maxweight > minweight + 1:
			mw = (maxweight + minweight) // 2
			if self.canShipWithinDays(weights, D, mw):
				maxweight = mw
			else:
				minweight = mw
		if self.canShipWithinDays(weights, D, minweight):
			return minweight
		else:
			return maxweight


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		left = max(weights)
		right = sum(weights)

		def possible_with_capacity(c):
			days = 1
			total = 0
			for weight in weights:
				total += weight
				if total > c:
					total = weight
					days += 1
					if days > D:
						return False
			return True
		while left < right:
			cap = left + (right - left) // 2
			if possible_with_capacity(cap):
				right = cap
			else:
				left = cap + 1
		return left


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		maxVal = weights[0]
		sum = 0
		for weight in weights:
			if maxVal < weight:
				maxVal = weight
			sum += weight
		if D == len(weights):
			return maxVal
		if D == 1:
			return sum

		def validWeight(weight_try: int) -> bool:
			count = 0
			local_sum = 0
			for weight in weights:
				local_sum += weight
				if local_sum > weight_try:
					local_sum = weight
					count += 1
			return count < D
		left = maxVal
		right = sum
		result = 0
		while left <= right:
			mid = (left + right) // 2
			if validWeight(mid):
				result = mid
				right = mid - 1
			else:
				left = mid + 1
		return result


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def days_required(t):
			running_sum = 0
			days = 0
			for i in range(n):
				running_sum += weights[i]
				if running_sum > t:
					days += 1
					running_sum = weights[i]
			return days
		n = len(weights)
		(lo, hi) = (max(weights), sum(weights))
		while lo <= hi:
			capacity = (lo + hi) // 2
			if days_required(capacity) < D:
				hi = capacity - 1
			else:
				lo = capacity + 1
		return lo


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def canShip(maxCapacity):
			days = 0
			cur = 0
			for w in weights:
				if cur + w <= maxCapacity:
					cur += w
				else:
					cur = w
					days += 1
			days += 1
			return days <= D
		l = max(weights)
		r = sum(weights)
		while l < r:
			mid = (l + r) // 2
			if canShip(mid):
				r = mid
			else:
				l = mid + 1
		return l


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		min_cap = max(weights)
		max_cap = sum(weights)
		while min_cap < max_cap:
			cap = (min_cap + max_cap) // 2
			remainder = cap
			days = 1
			for i in range(len(weights)):
				if weights[i] > remainder:
					remainder = cap
					days += 1
				remainder -= weights[i]
			if days > D:
				min_cap = cap + 1
			else:
				max_cap = cap
		return min_cap


class Solution:

	def check(self, w, cap, D):
		c = 0
		d = 0
		i = 0
		while i < len(w):
			c += w[i]
			if c > cap:
				d += 1
				c = w[i]
			i += 1
		return d

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		(l, h) = (max(weights), sum(weights))
		while l <= h:
			m = (l + h) // 2
			if self.check(weights, m, D) >= D:
				l = m + 1
			else:
				h = m - 1
		return l


import math

class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		sum_ = sum(weights)
		max_weight = max(weights)
		if D == 1:
			return sum_

		def check_capacity_enough(weights, D, capac):
			temp_cargo = 0
			count_ships = 1
			for i in range(len(weights)):
				if temp_cargo + weights[i] <= capac:
					temp_cargo += weights[i]
				else:
					count_ships += 1
					if count_ships > D:
						return False
					temp_cargo = weights[i]
			return True

		def binary_search(weights, D, sum_, max_weight):
			left = max(math.floor(sum_ / D) - 1, max_weight - 1)
			right = max(math.ceil(2 * sum_ / D) + 1, max_weight + 3)
			while right - left >= 2:
				mid = (left + right) // 2
				if mid >= max_weight and check_capacity_enough(weights, D, mid):
					right = mid
				else:
					left = mid
			return right
		return binary_search(weights, D, sum_, max_weight)


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def condition(capacity):
			day = 1
			increaseCap = 0
			i = 0
			while i < len(weights):
				increaseCap += weights[i]
				if increaseCap > capacity:
					increaseCap = weights[i]
					day += 1
					if day > D:
						return False
				i += 1
			return True
		(left, right) = (max(weights), sum(weights))
		while left < right:
			mid = left + (right - left) // 2
			if condition(mid):
				right = mid
			else:
				left = mid + 1
		return left


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def checkDays(capacity):
			days = 1
			cc = 0
			for num in weights:
				if cc == capacity:
					cc = 0
					days += 1
				if num > capacity:
					return 999999
				cc += num
				if cc > capacity:
					days += 1
					cc = num
			return days
		hi = max(weights) * len(weights)
		low = 0
		while low < hi:
			guess = int((low + hi) / 2)
			print(low, hi, guess)
			d = checkDays(guess)
			if d > D:
				low = guess + 1
			else:
				hi = guess
		return low


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def canCarry(cap):
			(cur, d) = (0, 1)
			for w in weights:
				if w > cap:
					return False
				cur += w
				if cur > cap:
					cur = w
					d += 1
				if d > D:
					return False
			return cur <= cap
		(l, r) = (max(weights), sum(weights))
		while l < r:
			m = (l + r) // 2
			if canCarry(m):
				r = m
			else:
				l = m + 1
		return l


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		n = len(weights)
		left = 1
		right = sum(weights)

		def works(capacity):
			tot_days = 0
			i = 0
			while i < n:
				j = i
				curr_load = 0
				while j < n and curr_load + weights[j] <= capacity:
					curr_load += weights[j]
					j += 1
				if j == i:
					return False
				i = j
				tot_days += 1
			return tot_days <= D
		while left <= right:
			mid = (left + right) // 2
			if works(mid):
				right = mid - 1
			else:
				left = mid + 1
		return left


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		total = sum(weights)
		(lo, hi) = (max(max(weights), total // D), total)
		n = len(weights)

		def valid(x):
			i = days = 0
			while i < n:
				S = 0
				while i < n and S + weights[i] <= x:
					S += weights[i]
					i += 1
				days += 1
			return days <= D
		while lo < hi:
			mid = (lo + hi) // 2
			print(mid)
			if valid(mid):
				hi = mid
			else:
				lo = mid + 1
		return lo


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		(l, r) = (max(weights), sum(weights))
		while l < r:
			mid = (l + r) // 2
			cnt = 1
			cursum = 0
			for weight in weights:
				if cursum + weight <= mid:
					cursum += weight
				else:
					cnt += 1
					cursum = weight
			if cnt <= D:
				r = mid
			else:
				l = mid + 1
		return r


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		if not weights:
			return 0
		NUM_PACKAGES = len(weights)
		if NUM_PACKAGES == 1:
			return weights[0]
		elif NUM_PACKAGES == 2:
			return max(weights[0], weights[1])
		(max_capacity, min_capacity) = (0, 0)
		for weight in weights:
			max_capacity += weight
			min_capacity = weight if weight > min_capacity else min_capacity

		def possible(capacity):
			curr_weight = 0
			curr_days = 0
			package_index = 0
			while package_index < NUM_PACKAGES:
				if curr_weight + weights[package_index] > capacity:
					curr_days += 1
					if curr_days > D:
						return False
					curr_weight = 0
				curr_weight += weights[package_index]
				package_index += 1
			curr_days += 1
			if curr_days > D:
				return False
			return True
		least_capacity = 0
		while min_capacity <= max_capacity:
			mid_point = (min_capacity + max_capacity) // 2
			if possible(mid_point):
				least_capacity = mid_point
				max_capacity = mid_point - 1
			else:
				min_capacity = mid_point + 1
		return least_capacity


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def package(weights, limit):
			kk = 0
			count = 1
			for i in range(len(weights)):
				kk = kk + weights[i]
				if kk > limit:
					kk = weights[i]
					count = count + 1
			return count
		lindex = max(weights)
		rindex = lindex * len(weights) // D
		while lindex < rindex:
			mid = lindex + (rindex - lindex) // 2
			capacity = mid
			Dstar = package(weights, capacity)
			if Dstar > D:
				lindex = mid + 1
			else:
				rindex = mid
		return lindex


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		(lo, hi) = (0, 9999999)
		ans = -1
		N = len(weights)
		for w in weights:
			lo = max(lo, w)

		def poss(val):
			(n, cnt, sum) = (0, 1, 0)
			while n < N:
				if sum + weights[n] <= val:
					sum += weights[n]
				else:
					cnt += 1
					sum = weights[n]
				n += 1
			return cnt
		while lo <= hi:
			mid = lo + (hi - lo) // 2
			nn = poss(mid)
			if nn <= D:
				ans = mid
				hi = mid - 1
			else:
				lo = mid + 1
		return ans


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		l = max(weights)
		r = 10 ** 9
		while l < r:
			m = l + (r - l) // 2
			days = 1
			s = 0
			for i in range(len(weights)):
				if s + weights[i] > m:
					days += 1
					s = weights[i]
				else:
					s += weights[i]
			if days <= D:
				r = m
			else:
				l = m + 1
		return l


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def countDays(weights, capacity):
			(l, r, cnt, sumv) = (0, 0, 0, 0)
			while r < len(weights):
				sumv += weights[r]
				if sumv > capacity:
					cnt += 1
					l = r
					sumv = 0
				else:
					r += 1
			if sumv:
				cnt += 1
			return cnt
		(maxv, sumv) = (max(weights), sum(weights))
		(left, right) = (maxv, sumv)
		while left < right:
			mid = (left + right) // 2
			days = countDays(weights, mid)
			if days > D:
				left = mid + 1
			else:
				right = mid
		return left


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		(left, right) = (max(weights), sum(weights))
		while left < right:
			mid = (left + right) // 2
			if self.can_achieve(weights, mid, D):
				right = mid
			else:
				left = mid + 1
		return left

	def can_achieve(self, weights, max_weight, D):
		i = 0
		total = 0
		days = 0
		while i < len(weights):
			if total + weights[i] > max_weight:
				total = 0
				days += 1
			total += weights[i]
			i += 1
		days += 1
		return days <= D


class Solution:

	def trips(self, l, c):
		currSum = 0
		(t, i) = (0, 0)
		n = len(l)
		while i < n:
			if currSum + l[i] > c:
				currSum = 0
				t = t + 1
			else:
				currSum = currSum + l[i]
				i = i + 1
		return t + 1

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		low = max(weights)
		high = sum(weights)
		while low < high:
			mid = int(low + (high - low) / 2)
			if self.trips(weights, mid) <= D:
				high = mid
			else:
				low = mid + 1
		return low


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		if not weights:
			return 0
		(left, right) = (max(weights), sum(weights))
		while left < right:
			mid = left + (right - left) // 2
			if self.checkValidPartition(weights, mid, D):
				right = mid
			else:
				left = mid + 1
		return left

	def checkValidPartition(self, weights, capacity, D):
		count = 1
		cur_sum = 0
		for w in weights:
			if cur_sum + w > capacity:
				count += 1
				cur_sum = 0
			cur_sum += w
		return count <= D


class Solution:

	def shipWithinDays(self, weights, D: int) -> int:
		if not weights or not D:
			return 0
		(lo, hi) = (max(weights), sum(weights))
		ans = 0
		while lo <= hi:
			mid = lo + (hi - lo) // 2
			res = self.validate(weights, D, mid)
			if res == 1:
				ans = mid
				hi = mid - 1
			else:
				lo = mid + 1
		return ans

	def validate(self, weights, D, capacity):
		count = 0
		w = 0
		D -= 1
		while w < len(weights):
			if count + weights[w] <= capacity:
				count += weights[w]
			else:
				count = weights[w]
				D -= 1
				if D < 0:
					break
			w += 1
		if w == len(weights):
			return 1
		else:
			return -1


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		hlim = sum(weights)
		llim = max(weights)

		def isValid(cap, days):
			temp = 0
			x = 0
			while x < len(weights):
				temp += weights[x]
				if temp > cap:
					x -= 1
					temp = 0
					days -= 1
				x += 1
			return days >= 1
		ans = -1
		while llim <= hlim:
			mid = (llim + hlim) // 2
			if isValid(mid, D):
				ans = mid
				hlim = mid - 1
			else:
				llim = mid + 1
		return ans


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		(l, r) = (max(weights), sum(weights))
		while l < r:
			(m, n, c) = ((l + r) / 2, 1, 0)
			for z in weights:
				if c + z > m:
					n += 1
					c = 0
				c += z
			if n > D:
				l = m + 1
			else:
				r = m
		return int(l)


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		left = max(weights)
		right = sum(weights) + 1
		while left < right:
			mid = left + (right - left) // 2
			legal = self.evaluate(weights, D, mid)
			if legal:
				right = mid
			else:
				left = mid + 1
		return left

	def evaluate(self, weights, D, weight_capacity):
		cursum = 0
		days = 0
		for val in weights:
			if val > weight_capacity:
				return False
			if val + cursum > weight_capacity:
				days += 1
				cursum = val
			else:
				cursum += val
		if cursum != 0:
			days += 1
		if days > D:
			return False
		return True


class Solution:

	def canShipAllPackages(self, weight_capacity, D, weights):
		days_needed = 1
		current_day_weight = 0
		i = 0
		while i < len(weights):
			weight = weights[i]
			if current_day_weight + weight <= weight_capacity:
				current_day_weight += weight
				i += 1
			else:
				current_day_weight = 0
				days_needed += 1
		return days_needed <= D

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		if len(weights) == 0:
			return 0
		left = max(weights)
		right = sum(weights)
		while left < right:
			mid = (left + right) // 2
			if self.canShipAllPackages(mid, D, weights):
				right = mid
			else:
				left = mid + 1
		return left


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		n = len(weights)

		def count(c: int) -> int:
			ans = 1
			curr = weights[0]
			for i in range(1, n):
				if curr + weights[i] > c:
					ans += 1
					curr = weights[i]
				else:
					curr += weights[i]
			return ans
		l = max(weights)
		r = sum(weights)
		while l < r:
			m = (l + r) // 2
			if count(m) > D:
				l = m + 1
			else:
				r = m
		return l


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		(minCapacity, maxCapacity) = (max(weights), sum(weights))
		while minCapacity < maxCapacity:
			capacityCandidate = (minCapacity + maxCapacity) // 2
			(daysToShip, currentCargo) = (1, 0)
			for newCargo in weights:
				if currentCargo + newCargo > capacityCandidate:
					currentCargo = 0
					daysToShip += 1
				currentCargo += newCargo
			if daysToShip <= D:
				maxCapacity = capacityCandidate
			else:
				minCapacity = capacityCandidate + 1
		return minCapacity


class Solution:

	def get_day(self, weights, cap):
		i = 0
		res = 0
		wei = 0
		while i < len(weights):
			if wei + weights[i] <= cap:
				wei += weights[i]
				i += 1
			else:
				wei = 0
				res += 1
		return res + 1

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		(start, end) = (max(weights), sum(weights))
		while start < end:
			mid = (start + end) // 2
			days = self.get_day(weights, mid)
			if days <= D:
				end = mid
			else:
				start = mid + 1
		return end


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def timeConsumption(limit):
			days = totalWeight = 0
			for weight in weights:
				if totalWeight + weight > limit:
					days += 1
					totalWeight = weight
				else:
					totalWeight += weight
			return days + 1
		left = max(weights)
		right = sum(weights) + 1
		while left < right:
			mid = left + (right - left) // 2
			time = timeConsumption(mid)
			if time > D:
				left = mid + 1
			else:
				right = mid
		return left


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def condition(w) -> bool:
			(curr, k) = (0, 0)
			count = 0
			while k < len(weights):
				if curr + weights[k] > w:
					count += 1
					if count > D:
						return False
					curr = 0
				curr += weights[k]
				k += 1
			return count + 1 <= D
		(left, right) = (max(weights), sum(weights))
		while left < right:
			mid = left + (right - left) // 2
			if condition(mid):
				right = mid
			else:
				left = mid + 1
		return left


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		left = int(sum(weights) / D)
		right = max(weights) * len(weights) / D

		def is_valid(weights, D, capacity):
			cur = capacity
			day = 0
			for w in weights:
				if cur + w <= capacity:
					cur += w
				else:
					cur = 0
					if capacity < w:
						return False
					else:
						cur = w
						day += 1
			if day <= D:
				return True
			return False
		while left <= right:
			mid = left + (right - left) // 2
			if is_valid(weights, D, mid):
				right = mid - 1
			else:
				left = mid + 1
		return int(left)


class Solution:

	def canShip(self, w, d, cap):
		i = 0
		res = 0
		while i < len(w):
			if w[i] > cap:
				return False
			remain = cap
			while i < len(w) and remain >= w[i]:
				remain -= w[i]
				i += 1
			res += 1
		return res <= d

	def shipWithinDays(self, w: List[int], D: int) -> int:
		if len(w) == 0:
			return 0
		start = max(w)
		end = sum(w)
		while start < end:
			mid = int((end - start) / 2) + start
			if self.canShip(w, D, mid):
				end = mid
			else:
				start = mid + 1
		return start


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def check_possible(capacity):
			count = 0
			i = 0
			while i < len(weights):
				count += 1
				if count > D or weights[i] > capacity:
					return False
				curr_ship = 0
				while i < len(weights) and weights[i] + curr_ship <= capacity:
					curr_ship += weights[i]
					i += 1
			return True
		tot = 0
		largest = 0
		for w in weights:
			tot += w
			largest = max(largest, w)
		l = largest
		r = tot
		if check_possible(l):
			return l
		while l < r - 1:
			mid = (l + r) // 2
			if check_possible(mid):
				r = mid
			else:
				l = mid
		return r


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def no_of_days(weights, W, D):
			count = 1
			su = 0
			i = 0
			while i < len(weights):
				if su + weights[i] <= W:
					su += weights[i]
					i += 1
				else:
					su = weights[i]
					i += 1
					count += 1
			return count

		def binary(weight, i, j, D):
			ans = 0
			while i <= j:
				mid = int((i + j) / 2)
				d = no_of_days(weight, mid, D)
				if d <= D:
					ans = mid
					j = mid - 1
				else:
					i = mid + 1
			return ans
		wi = max(weights)
		wj = wi * len(weights)
		a = binary(weights, wi, wj, D)
		return a


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		(l, r) = (max(weights), sum(weights))
		while l <= r:
			m = l + (r - l) // 2
			if self.loadBalancer(weights, m) > D:
				l = m + 1
			elif self.loadBalancer(weights, m) <= D:
				r = m - 1
		return l

	def loadBalancer(self, weights, target):
		(c, sum_) = (1, 0)
		for i in weights:
			if sum_ + i > target:
				c += 1
				sum_ = 0
			sum_ += i
		return c


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		lo = max(weights)
		hi = sum(weights)
		res = hi
		while lo <= hi:
			mid = lo + (hi - lo) // 2
			days = 0
			curr_weight = 0
			for i in range(len(weights)):
				if curr_weight + weights[i] > mid:
					days += 1
					curr_weight = weights[i]
				else:
					curr_weight += weights[i]
			days += 1
			if days <= D:
				res = mid
				hi = mid - 1
			else:
				lo = mid + 1
		return res


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def possible(cap):
			d = D
			i = 0
			while i < len(weights) and weights[i] <= cap:
				cur = 0
				while i < len(weights) and cur + weights[i] <= cap:
					cur += weights[i]
					i += 1
				d -= 1
			if i < len(weights):
				return False
			return d >= 0
		total = sum(weights)
		(l, r) = (1, total)
		ans = float('inf')
		while l <= r:
			m = l + (r - l) // 2
			if possible(m):
				r = m - 1
				ans = min(ans, m)
			else:
				l = m + 1
		return ans


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def can(K):
			i = 0
			days = 0
			while i < len(weights) and days <= D + 1:
				k = K
				days += 1
				while i < len(weights) and k >= weights[i]:
					k -= weights[i]
					i += 1
			return days <= D
		(l, r) = (1, sum(weights))
		while l < r:
			mid = (l + r) // 2
			if can(mid):
				r = mid
			else:
				l = mid + 1
		return l


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def possible(cap):
			s = 0
			ship = 0
			i = 0
			while i < len(weights):
				s = s + weights[i]
				if s > cap:
					ship = ship + 1
					s = 0
				elif s < cap:
					i = i + 1
				else:
					ship = ship + 1
					s = 0
					i = i + 1
			if s == 0:
				return ship <= D
			else:
				return ship + 1 <= D
		lo = max(weights)
		hi = sum(weights)
		while lo <= hi:
			mid = lo + (hi - lo) // 2
			if possible(mid):
				hi = mid - 1
			else:
				lo = mid + 1
		return lo


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		SUM = sum(weights)
		MAX = max(weights)
		h = SUM
		l = max(MAX, SUM // D) - 1

		def canDo(arr, D, num):
			j = 0
			for i in range(D):
				total = 0
				while j < len(arr) and total + arr[j] <= num:
					total += arr[j]
					j += 1
				if j == len(arr):
					return True
				elif total == 0:
					return False
			return j == len(arr)
		while h > l + 1:
			m = (l + h) // 2
			if canDo(weights, D, m):
				h = m
			else:
				l = m
		return l + 1


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		left = 1
		right = max(weights) * len(weights)
		while left < right:
			mid = (left + right) // 2
			if self.possible(weights, D, mid):
				right = mid
			else:
				left = mid + 1
		return left

	def possible(self, weights, D, mid):
		cnt = 0
		tmp = 0
		for w in weights:
			if w > mid:
				return False
			if tmp + w > mid:
				tmp = w
				cnt += 1
			else:
				tmp += w
		if tmp != 0:
			cnt += 1
		return cnt <= D


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def ship_capacity(weights, D, capacity):
			days = 0
			sum_weights = 0
			for i in range(len(weights) - 1):
				sum_weights += weights[i]
				if sum_weights + weights[i + 1] > capacity:
					days += 1
					sum_weights = 0
			return days <= D - 1
		start = max(weights)
		end = sum(weights)
		while start <= end:
			mid = (start + end) // 2
			if ship_capacity(weights, D, mid):
				end = mid - 1
			else:
				start = mid + 1
		return start


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def checkIfCanShipWithinDDays(weights: List[int], D: int, capacity: int) -> bool:
			(b, count, total) = (0, 0, 0)
			while b < len(weights):
				while total + weights[b] <= capacity:
					total += weights[b]
					b += 1
					if b == len(weights):
						count += 1
						return count <= D
				count += 1
				total = 0
			return count <= D
		total = sum(weights)
		lb = max(weights)
		ub = total
		while lb < ub:
			mid = lb + (ub - lb) // 2
			if checkIfCanShipWithinDDays(weights, D, mid):
				ub = mid
			else:
				lb = mid + 1
		return lb


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		left = max(weights)
		right = sum(weights)
		while left + 1 < right:
			mid = left + (right - left) // 2
			print(mid)
			curr = 0
			res = 1
			for w in weights:
				if curr + w > mid:
					res += 1
					curr = w
				else:
					curr += w
			if res > D:
				left = mid
			else:
				right = mid
		res = 1
		curr = 0
		for w in weights:
			if curr + w > left:
				res += 1
				curr = w
			else:
				curr += w
		if res <= D:
			return left
		return right


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		self.weight = weights
		self.D = D
		hi = sum(weights)
		lo = 1
		while hi != lo:
			mid = (hi + lo) // 2
			if self.if_fit(mid):
				hi = mid
			else:
				lo = mid + 1
		return hi

	def if_fit(self, cap):
		d = 1
		count = 0
		for val in self.weight:
			if val > cap:
				return False
			if val + count <= cap:
				count += val
			else:
				count = val
				d += 1
				if d > self.D:
					return False
		return True


class Solution:

	def canFinish(self, weights, D, C):
		index = 0
		for _ in range(D):
			total = 0
			while index < len(weights) and total + weights[index] <= C:
				total += weights[index]
				index += 1
			if index == len(weights):
				return True
		return False

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		l = 0
		r = sum(weights)
		while l < r - 1:
			m = l + (r - l) // 2
			if self.canFinish(weights, D, m):
				r = m
			else:
				l = m + 1
		if self.canFinish(weights, D, l):
			return l
		return r


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		(left, right) = (max(weights), max(weights) * len(weights) // D)

		def checkShipping(capacity):
			days = 1
			total_weight = 0
			for weight in weights:
				if weight > capacity or days > D:
					return False
				if weight + total_weight > capacity:
					total_weight = weight
					days += 1
				else:
					total_weight += weight
			return days <= D
		while left <= right:
			mid = left + (right - left) // 2
			if checkShipping(mid):
				right = mid - 1
			else:
				left = mid + 1
		return left


class Solution:

	def can_ship(self, weights, D, max_weight):
		i = 0
		s = 0
		while i < len(weights) and D > 0:
			s = 0
			while i < len(weights) and s <= max_weight:
				s += weights[i]
				if s > max_weight:
					break
				i += 1
			D -= 1
		if D == 0 and i < len(weights):
			return False
		return True

	def shipWithinDays(self, weights, D):
		left = min(weights)
		right = sum(weights)
		while left < right:
			mid = int((left + right) / 2)
			if self.can_ship(weights, D, mid):
				right = mid
			else:
				left = mid
			if right == left + 1:
				if self.can_ship(weights, D, left):
					return left
				else:
					return right
		return mid


class Solution:

	def canShip(self, weights, capacity, D) -> bool:
		(cnt, i) = (0, 0)
		cum = 0
		while i < len(weights):
			if cum + weights[i] <= capacity:
				cum += weights[i]
				i += 1
			else:
				cnt += 1
				cum = 0
		cnt += 1
		return cnt <= D

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		(l, r) = (max(weights), sum(weights))
		while l < r:
			mid = (l + r) // 2
			if self.canShip(weights, mid, D):
				r = mid
			else:
				l = mid + 1
		return r


def check(arr, mid, D):
	count = 1
	n = len(arr)
	cur_sum = 0
	for i in range(n):
		if cur_sum + arr[i] > mid:
			count += 1
			cur_sum = 0
		cur_sum += arr[i]
		if count > D:
			return False
	return count <= D

class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		max_weight = sum(weights)
		min_weight = max(weights)
		ans = float('inf')
		while min_weight <= max_weight:
			mid = int((max_weight + min_weight) / 2)
			if check(weights, mid, D) == True:
				ans = min(ans, mid)
				max_weight = mid - 1
			else:
				min_weight = mid + 1
		return ans


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def test(capacity):
			count = 0
			current_sum = 0
			i = 0
			while i < len(weights) and count < D:
				while i < len(weights) and current_sum + weights[i] <= capacity:
					current_sum += weights[i]
					i += 1
				count += 1
				current_sum = 0
			return count <= D and i == len(weights)
		(l, r) = (1, sum(weights))
		while l < r:
			mid = (l + r) // 2
			if test(mid):
				r = mid
			else:
				l = mid + 1
		return l


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		(l, r) = (max(weights), sum(weights))
		while l < r:
			mid = (l + r) // 2
			d = self.check(weights, mid)
			if d > D:
				(l, r) = (mid + 1, r)
			else:
				(l, r) = (l, mid)
		return l

	def check(self, weights, size):
		c = 0
		i = 0
		days = 0
		while True:
			if i == len(weights):
				break
			while i < len(weights) and c + weights[i] <= size:
				c += weights[i]
				i += 1
			c = 0
			days += 1
		return days


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		maxCap = sum(weights)
		minCap = max(weights)
		ans = maxCap
		lo = minCap
		hi = maxCap
		while lo <= hi:
			mi = lo + (hi - lo) // 2
			daysLeft = D
			dailyCap = mi
			i = 0
			while i < len(weights) and daysLeft:
				wei = weights[i]
				if wei > dailyCap:
					daysLeft -= 1
					dailyCap = mi
				elif wei == dailyCap:
					daysLeft -= 1
					dailyCap = mi
					i += 1
				else:
					dailyCap -= wei
					i += 1
			if i == len(weights):
				ans = min(ans, mi)
				hi = mi - 1
			else:
				lo = mi + 1
		return ans


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def condition(k):
			(ind, load, days) = (0, 0, 0)
			while ind < len(weights):
				if weights[ind] + load <= k:
					load += weights[ind]
					ind += 1
				else:
					load = 0
					days += 1
			return days + 1 <= D
		(left, right) = (max(weights), sum(weights))
		while left < right:
			mid = left + (right - left) // 2
			if condition(mid):
				right = mid
			else:
				left = mid + 1
		return left


class Solution:

	def shipWithinDays(self, arr: List[int], D: int) -> int:

		def count(arr, x):
			res = i = 0
			while i < len(arr):
				z = 0
				while i < len(arr) and z + arr[i] <= x:
					z += arr[i]
					i += 1
				res += 1
			return res
		end = start = 0
		for i in arr:
			end += i
			start = max(start, i)
		while start <= end:
			mid = start + (end - start) // 2
			if count(arr, mid) > D:
				start = mid + 1
			else:
				out = mid
				end = mid - 1
		return out


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		s = max(weights)
		e = max(weights) * len(weights) // D

		def dayCount(weights, cap, D):
			day = 1
			total = 0
			for i in range(len(weights)):
				if total + weights[i] <= cap:
					total += weights[i]
				else:
					day += 1
					total = weights[i]
			return day <= D
		while s <= e:
			mid = (s + e) // 2
			if dayCount(weights, mid, D):
				e = mid - 1
			else:
				s = mid + 1
		return s


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		l = 0
		r = sum(weights)
		best = r
		while l <= r:
			mid = l + (r - l) // 2
			if self.works(mid, weights, D):
				best = mid
				r = mid - 1
			else:
				l = mid + 1
		return best

	def works(self, cap, weights, d):
		if cap < max(weights):
			return False
		idx = 0
		total_days = 0
		while idx < len(weights):
			cur_cap = 0
			while cur_cap < cap and idx < len(weights):
				if cur_cap + weights[idx] > cap:
					break
				cur_cap += weights[idx]
				idx += 1
			total_days += 1
		return total_days <= d


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		cap_min = max(weights)
		cap_max = sum(weights)
		while cap_min < cap_max:
			cap_mid = (cap_min + cap_max) // 2
			days = self._cal_num_of_days(weights, cap_mid)
			if days > D:
				cap_min = cap_mid + 1
			elif days < D:
				cap_max = cap_mid
			elif days == D:
				cap_max = cap_mid
		return cap_min

	def _cal_num_of_days(self, weights: List[int], cap: int) -> int:
		days = 0
		i = 0
		while i < len(weights):
			current_load = 0
			while i < len(weights) and current_load + weights[i] <= cap:
				current_load += weights[i]
				i += 1
			days += 1
		return days


class Solution:

	def check(self, weights: List[int], D: int, cap: int) -> bool:
		load = 1
		total = 0
		for i in range(len(weights)):
			total += weights[i]
			if i != len(weights) - 1:
				if total + weights[i + 1] > cap:
					total = 0
					load += 1
					if load > D:
						return False
		if load <= D:
			return True

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		lo = max(weights)
		hi = sum(weights)
		while lo < hi:
			mid = lo + (hi - lo) // 2
			if self.check(weights, D, mid):
				hi = mid
			else:
				lo = mid + 1
		return lo


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def test(x):
			(times, i) = (0, 0)
			while i < len(weights):
				times += 1
				cur = 0
				while i < len(weights) and cur + weights[i] <= x:
					cur += weights[i]
					i += 1
			return times
		(l, r) = (max(weights), sum(weights))
		while l <= r:
			mid = (l + r) // 2
			days = test(mid)
			if days <= D:
				r = mid - 1
			else:
				l = mid + 1
		if days > D:
			mid += 1
		return mid


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def days_taken(capacity, arr):
			days = 0
			i = 0
			while i < len(arr):
				j = i
				bucket = capacity
				days += 1
				while j < len(arr) and arr[j] <= bucket and (bucket > 0):
					bucket -= arr[j]
					j += 1
				i = j
			return days
		low = max(weights)
		high = sum(weights)
		while low < high:
			mid = (low + high) // 2
			days_by_mid = days_taken(mid, weights)
			if days_by_mid <= D:
				high = mid
			else:
				low = mid + 1
		return low


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		(start, end) = (max(weights), sum(weights) + 1)
		while start + 1 < end:
			mid = start + (end - start) // 2
			if self._can_ship(weights, mid, D):
				end = mid
			else:
				start = mid
		return start if self._can_ship(weights, start, D) else end

	def _can_ship(self, weights, capacity, D):
		days_needed = 0
		i = 0
		while i < len(weights):
			curr_w = 0
			while i < len(weights) and curr_w + weights[i] <= capacity:
				curr_w += weights[i]
				i += 1
			days_needed += 1
		return days_needed <= D


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def feasible(w):
			i = 0
			for day in range(D):
				ship_w = 0
				while i < len(weights):
					if w - ship_w >= weights[i]:
						ship_w += weights[i]
					else:
						break
					i += 1
			return i == len(weights)
		(left, right) = (max(weights), sum(weights))
		while left < right:
			mid = left + right >> 1
			if feasible(mid):
				right = mid
			else:
				left = mid + 1
		return left


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def check_capacity(capacity) -> bool:
			days = 1
			ship_weight = 0
			for weight in weights:
				ship_weight += weight
				if ship_weight > capacity:
					ship_weight = weight
					days += 1
					if days > D:
						return False
			return True
		left = max(weights)
		right = left * len(weights) // D
		while left < right:
			mid = left + (right - left) // 2
			if check_capacity(mid):
				right = mid
			else:
				left = mid + 1
		return left


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		memo = {}
		high = sum(weights)
		low = ceil(high / D)
		best = low
		mid = low + (high - low) // 2
		memo[mid] = is_possible(weights, mid, D)
		memo[mid + 1] = is_possible(weights, mid + 1, D)
		while memo[mid] or not memo[mid + 1]:
			if high == low and high == best:
				return best
			if not memo[mid]:
				low = mid + 1
			else:
				high = mid
			mid = low + (high - low) // 2
			if mid not in memo:
				memo[mid] = is_possible(weights, mid, D)
			if mid + 1 not in memo:
				memo[mid + 1] = is_possible(weights, mid + 1, D)
		return mid + 1

def is_possible(weights, max_w, D):
	total = 0
	for (i, weight) in enumerate(weights):
		if weight > max_w:
			return False
		if total + weight > max_w:
			total = 0
			D -= 1
			if D == 0:
				return False
		total += weight
	return True


class Solution:

	def possible(self, capacity):
		ret = 0
		cur = 0
		for w in self.weights:
			if w > capacity:
				return False
			if cur + w <= capacity:
				cur += w
			else:
				ret += 1
				cur = w
		if w > 0:
			ret += 1
		return ret <= self.D

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		self.weights = weights
		self.D = D
		(lo, hi) = (1, 1061109567)
		while lo <= hi:
			mid = lo + (hi - lo >> 1)
			if self.possible(mid):
				hi = mid - 1
			else:
				lo = mid + 1
		if self.possible(lo):
			return lo
		return lo + 1


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		l = max(weights)
		r = sum(weights)

		def canFitInD(m):
			n = 1
			current = 0
			for i in range(len(weights)):
				if current + weights[i] <= m:
					current += weights[i]
				else:
					n += 1
					current = weights[i]
					if n > D:
						return False
			return True
		while l < r:
			mid = l + (r - l) // 2
			if canFitInD(mid):
				r = mid
			else:
				l = mid + 1
		return l


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		n = len(weights)
		if not n:
			return n
		total = sum(weights)
		target = total // D
		(left, right) = (max(weights), total)

		def check(s, total, D):
			cur = 0
			i = 0
			while i < len(weights):
				w = weights[i]
				if cur + w > s:
					total -= cur
					D -= 1
					cur = 0
				else:
					cur += w
					i += 1
				if D == 1:
					if total > s:
						return False
					else:
						return True
			return True
		ans = total
		while left <= right:
			mid = (left + right + 1) // 2
			if check(mid, total, D):
				ans = min(ans, mid)
				right = mid - 1
			else:
				left = mid + 1
		return ans


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def check(capacity, D):
			d = 0
			i = 0
			c = capacity
			while d < D:
				if i == len(weights):
					return True
				if weights[i] <= c:
					if weights[i] > capacity:
						return False
					c -= weights[i]
					i += 1
				else:
					c = capacity
					d += 1
			return False
		l = 0
		r = max(weights) * len(weights)
		while l < r:
			mid = l + (r - l) // 2
			if check(mid, D):
				r = mid
			else:
				l = mid + 1
		return l


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def isOK(weights, D, w):
			count = 1
			weight = 0
			for i in range(0, len(weights)):
				if weights[i] > w or count > D:
					return False
				if weight + weights[i] > w:
					count += 1
					weight = 0
				weight += weights[i]
			if count <= D:
				return True
			else:
				return False
		left = max(weights)
		right = sum(weights)
		while left <= right:
			middle = (left + right) // 2
			if isOK(weights, D, middle) == True:
				right = middle - 1
			else:
				left = middle + 1
		return left


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def good(cap):
			(i, tmp, ans) = (0, 0, 1)
			while i < len(a):
				if tmp + a[i] <= cap:
					tmp += a[i]
				else:
					ans += 1
					tmp = a[i]
				i += 1
			return ans <= D
		a = weights
		(lo, hi) = (max(a), sum(a))
		while lo < hi:
			mid = (lo + hi) // 2
			if good(mid):
				hi = mid
			else:
				lo = mid + 1
		return lo


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def helper(w):
			i = 0
			cnt = 0
			while cnt < D:
				curr = 0
				while i < len(weights):
					if curr + weights[i] <= w:
						curr += weights[i]
						i += 1
					else:
						break
				cnt += 1
			return False if i != len(weights) else True
		(l, r) = (max(weights), sum(weights))
		while l <= r:
			mid = (l + r) // 2
			if helper(mid):
				r = mid - 1
			else:
				l = mid + 1
		return l


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		(low, high) = (max(weights), sum(weights))
		while low < high:
			mid = low + (high - low) // 2
			d = 1
			curr_sum = 0
			for idx in range(len(weights)):
				if curr_sum + weights[idx] > mid:
					d += 1
					curr_sum = 0
				curr_sum += weights[idx]
			if d <= D:
				high = mid
			else:
				low = mid + 1
		return low


from typing import List
import bisect

class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		l = min(weights)
		r = max(weights) * len(weights)

		def isOk(capacity):
			item = 0
			day = 0
			while item < len(weights):
				s = 0
				while True:
					if weights[item] > capacity:
						return False
					if s + weights[item] > capacity:
						break
					else:
						s = s + weights[item]
						item += 1
					if item >= len(weights):
						break
				day += 1
			return day <= D
		print(isOk(15))
		while r - l > 1:
			mid = l + (r - l) // 2
			if isOk(mid):
				r = mid
			else:
				l = mid
		return r
print(Solution().shipWithinDays([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5))


def isOK(cap, weights, D):
	cnt = 1
	total = 0
	for i in range(len(weights)):
		if total + weights[i] > cap:
			cnt += 1
			total = weights[i]
		else:
			total += weights[i]
	return cnt <= D

class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		(left, right) = (max(weights), max(weights) * len(weights) // D)
		while left <= right:
			mid = (right + left) // 2
			if isOK(mid, weights, D):
				right = mid - 1
			else:
				left = mid + 1
		return left


from typing import List

class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		l = -1
		r = max(weights) * len(weights)

		def isOk(capacity):
			item = 0
			day = 0
			while item < len(weights):
				s = 0
				while True:
					if weights[item] > capacity:
						return False
					if s + weights[item] > capacity:
						break
					else:
						s = s + weights[item]
						item += 1
					if item >= len(weights):
						break
				day += 1
			return day <= D
		while r - l > 1:
			mid = l + (r - l) // 2
			if isOk(mid):
				r = mid
			else:
				l = mid
		return r


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		mini = max(weights)
		maxi = sum(weights)
		if len(weights) == 1:
			return weights[0]
		while maxi >= mini:
			mid = (maxi + mini) // 2
			if self.check(weights, mid) < D:
				maxi = mid - 1
			elif self.check(weights, mid) > D:
				mini = mid + 1
			else:
				maxi = mid - 1
			print(mini)
		return mini

	def check(self, piles, num):
		res = 0
		i = 0
		count = 0
		while i < len(piles):
			if res + piles[i] < num:
				res += piles[i]
			elif res + piles[i] == num:
				res = 0
				count += 1
			else:
				res = piles[i]
				count += 1
			i += 1
		count = count if res == 0 else count + 1
		return count


class Solution:

	def possibleWithinDays(self, weights, D, capacity):
		x = 0
		i = 1
		total = 0
		while i <= D:
			current_sum = 0
			while x < len(weights) and current_sum + weights[x] <= capacity:
				current_sum += weights[x]
				total += weights[x]
				x += 1
			i += 1
		if total >= sum(weights):
			return True
		return False

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		total_sum = sum(weights)
		left = 0
		right = total_sum
		while left < right:
			middle = (left + right) // 2
			aux = self.possibleWithinDays(weights, D, middle)
			if aux:
				right = middle
			else:
				left = middle + 1
		return left


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		sums = [0] * (len(weights) + 1)
		for i in range(len(weights)):
			sums[i + 1] = weights[i] + sums[i]

		def backtracking(i, cap, d):
			if i == len(sums):
				return True
			if sums[-1] - sums[i - 1] > cap * d:
				return False
			j = i
			while j < len(sums):
				if sums[j] - sums[i - 1] > cap:
					break
				j += 1
			return backtracking(j, cap, d - 1)
		(l, h) = (max(weights), sum(weights))
		while l <= h:
			m = (l + h) // 2
			if backtracking(1, m, D):
				h = m - 1
			else:
				l = m + 1
		return l


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		n = len(weights)
		l = max(weights)
		r = n * max(weights)
		pre = [weights[0]]
		for i in range(1, len(weights)):
			pre.append(pre[-1] + weights[i])

		def checker(val) -> bool:
			x = 0
			y = 0
			j = 0
			i = 0
			while i < len(pre):
				x = pre[i] - y
				if x == val:
					x = 0
					y = pre[i]
					j += 1
					if j > D:
						return False
				elif x > val:
					x = 0
					y = pre[i - 1]
					i -= 1
					j += 1
					if j > D:
						return False
				i += 1
			if j == D and x != 0:
				return False
			return True
		while l < r:
			mid = (l + r) // 2
			if checker(mid) == True:
				r = mid
			else:
				l = mid + 1
		return l


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		end = sum(weights)
		start = end // D
		while start < end:
			mid = (start + end) // 2
			days = 1
			curr_sum = 0
			for i in range(len(weights)):
				if weights[i] > mid:
					days = D + 1
					break
				if curr_sum + weights[i] > mid:
					days += 1
					if days > D:
						break
					curr_sum = weights[i]
				else:
					curr_sum += weights[i]
			if start == mid:
				if days > D:
					return end
				else:
					return start
			if days > D:
				start = mid
			else:
				end = mid
		return start


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		preSum = [0]
		for weight in weights:
			preSum.append(weight + preSum[-1])
		N = len(weights)

		def shipWeights(ship):
			D0 = D
			start = 0
			l = 1
			r = N
			while D0 > 0 and l <= N:
				if ship >= preSum[r] - preSum[start]:
					l = r + 1
				while r > l:
					m = (l + r) // 2
					if preSum[m] - preSum[start] > ship:
						r = m
					else:
						l = m + 1
				D0 -= 1
				start = l - 1
				r = N
			if l == N + 1:
				return True
			return False
		wl = max(weights)
		wr = sum(weights)
		if D >= len(weights):
			return wl
		if D == 1:
			return wr
		while wr > wl:
			wm = (wr + wl) // 2
			if shipWeights(wm):
				wr = wm
			else:
				wl = wm + 1
		return wl


class Solution:

	def shipWithinDays(self, weights: List[int], days: int) -> int:
		self.weights = weights
		self.days = days
		(left, right) = (max(weights), sum(weights))
		while left < right:
			mid = left + (right - left) // 2
			if self.isFit(mid):
				right = mid
			else:
				left = mid + 1
		return left

	def isFit(self, capacity):
		weight_index = 0
		for day in range(0, self.days):
			current_capacity = capacity
			while current_capacity >= 0:
				if weight_index == len(self.weights):
					return True
				weight = self.weights[weight_index]
				if current_capacity - weight < 0:
					break
				else:
					current_capacity -= weight
					weight_index += 1
		return False


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		(start, end) = (max(weights), sum(weights))
		while start + 1 < end:
			mid = (start + end) // 2
			days = self.get_days(weights, mid)
			if days > D:
				start = mid + 1
			elif days <= D:
				end = mid
		if self.get_days(weights, start) <= D:
			return start
		else:
			return end

	def get_days(self, weights, cap):
		tot = 0
		res = 1
		i = 0
		while i < len(weights):
			tot += weights[i]
			if tot > cap:
				res += 1
				tot = 0
			else:
				i += 1
		return res


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def check(capacity):
			cur = ix = 0
			day = 1
			while ix < len(weights):
				if cur + weights[ix] == capacity:
					cur = 0
					day += 1
				elif cur + weights[ix] > capacity:
					cur = weights[ix]
					day += 1
				else:
					cur += weights[ix]
				ix += 1
			return ix == len(weights) and day <= D
		(left, right) = (max(weights), sum(weights))
		while left < right:
			mid = left + (right - left) // 2
			if check(mid):
				right = mid
			else:
				left = mid + 1
		return left


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def is_possible(C):
			if C < max(weights):
				return False
			(d, i, cap, n) = (1, -1, 0, len(weights))
			while d <= D:
				while i < n - 1 and cap + weights[i + 1] <= C:
					cap += weights[i + 1]
					i += 1
				d += 1
				cap = 0
			if i < n - 1:
				return False
			return True
		(left, right) = (0, sum(weights))
		while left < right:
			mp = left + (right - left) // 2
			if is_possible(mp):
				right = mp
			else:
				left = mp + 1
		return left


class Solution:

	def canBeFerried(self, weights: List[int], D: int, capacity: int) -> bool:
		(i, j, days) = (0, 0, 0)
		while i < len(weights):
			sum_ = 0
			j = 0
			while sum_ <= capacity:
				if i + j < len(weights):
					sum_ += weights[i + j]
				else:
					days += 1
					return days <= D
				j += 1
			days += 1
			if i == len(weights) - 1:
				break
			i += j - 1
			if days > D:
				return False
		return days <= D

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		low = max(weights)
		high = len(weights) * low
		while low < high:
			mid = (low + high) // 2
			if self.canBeFerried(weights, D, mid):
				high = mid
			else:
				low = mid + 1
		return low


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def canDo(k):
			d = 1
			curr = 0
			for w in weights:
				if w > k:
					return False
				curr += w
				if curr > k:
					d += 1
					curr = w
			return d <= D
		(l, r) = (0, 10 ** 18)
		while l < r:
			m = (l + r) // 2
			if canDo(m):
				r = m
			else:
				l = m + 1
		return l


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		(l, h) = (max(weights), sum(weights))
		while l < h:
			days = 1
			total_weight = 0
			capacity = (l + h) // 2
			for weight in weights:
				total_weight += weight
				if total_weight > capacity:
					days += 1
					total_weight = weight
			if days <= D:
				h = capacity
			else:
				l = capacity + 1
		return l


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		l = max(weights)
		r = sum(weights)

		def calc(cap):
			cnt = 0
			cur = 0
			for w in weights:
				cur += w
				if cur > cap:
					cur = w
					cnt += 1
			return cnt + 1 <= D
		while l < r:
			mid = (l + r) // 2
			good = calc(mid)
			if good:
				r = mid
			else:
				l = mid + 1
		return l


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		(left, right) = (max(weights), sum(weights))
		while left < right:
			mid = left + (right - left) // 2
			if self.__countDays(weights, mid) <= D:
				right = mid
			else:
				left = mid + 1
		return left

	def __countDays(self, weights, capacity):
		days = 0
		cur_w = 0
		for w in weights:
			cur_w += w
			if cur_w > capacity:
				days += 1
				cur_w = w
		return days + 1


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def check(W: int) -> bool:
			(count, total) = (1, 0)
			for w in weights:
				total += w
				if total > W:
					count += 1
					total = w
					if count > D:
						return False
			return True
		(left, right) = (max(weights), sum(weights))
		while left < right:
			mid = left + (right - left) // 2
			if check(mid):
				right = mid
			else:
				left = mid + 1
		return left


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def feasible(capacity):
			day = 1
			total = 0
			for weight in weights:
				total += weight
				if total > capacity:
					total = weight
					day += 1
					if day > D:
						return False
			return True
		(low, high) = (max(weights), sum(weights))
		while low < high:
			mid = low + (high - low) // 2
			if feasible(mid):
				high = mid
			else:
				low = mid + 1
		return low


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def feasible(capacity):
			days = 1
			total = 0
			for wt in weights:
				total += wt
				if total > capacity:
					total = wt
					days += 1
					if days > D:
						return False
			return True
		left = max(weights)
		right = sum(weights)
		while left < right:
			mid = left + (right - left) // 2
			if feasible(mid):
				right = mid
			else:
				left = mid + 1
		return left


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def isPossible(capacity):
			day = 1
			w = 0
			for wt in weights:
				w += wt
				if w > capacity:
					day += 1
					w = wt
			return day
		(start, end) = (max(max(weights), sum(weights) // D), sum(weights))
		while start < end:
			mid = start + (end - start) // 2
			days = isPossible(mid)
			if days <= D:
				end = mid
			elif days > D:
				start = mid + 1
		return start


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		n = len(weights)
		hi = 0
		lo = 0
		for w in weights:
			lo = max(lo, w)
			hi += w
		if D == 1:
			return hi
		while lo < hi:
			mid = lo + (hi - lo) // 2
			(cur, days) = (0, 1)
			for w in weights:
				cur += w
				if cur > mid:
					days += 1
					cur = w
			if days > D:
				lo = mid + 1
			else:
				hi = mid
		return lo


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		(l, r) = (max(weights), sum(weights))
		while l < r:
			mid = (r - l) // 2 + l
			day = self.weightWhetherWork(weights, mid)
			if day > D:
				l = mid + 1
			else:
				r = mid
		return l

	def weightWhetherWork(self, weights, mid):
		temp = mid
		day = 1
		for i in weights:
			if temp >= i:
				temp -= i
			else:
				temp = mid
				temp -= i
				day += 1
		return day


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		low = max(weights)
		high = sum(weights)
		total = 0
		parts = 1
		while low < high:
			total = 0
			parts = 1
			mid = int((low + high) / 2)
			for w in weights:
				if total + w <= mid:
					total = total + w
				else:
					total = w
					parts += 1
			if parts > D:
				low = mid + 1
			else:
				high = mid
		return low


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def calDays(weights, cap):
			days = 1
			acc_w = 0
			for w in weights:
				acc_w += w
				if acc_w > cap:
					days += 1
					acc_w = w
			return days
		lo = max(weights)
		hi = lo * len(weights) // D
		while lo < hi:
			med = lo + (hi - lo) // 2
			days = calDays(weights, med)
			if days <= D:
				hi = med
			else:
				lo = med + 1
		return hi


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def canship(cap):
			d = 1
			s = 0
			for w in weights:
				if s + w <= cap:
					s += w
				else:
					d += 1
					s = w
				if d > D:
					return False
			return True
		M = max(weights)
		if D == len(weights):
			return M
		(lo, hi) = (M - 1, sum(weights))
		while hi - lo > 1:
			h = (hi + lo) // 2
			if canship(h):
				hi = h
			else:
				lo = h
		return hi


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		(l, r) = (max(weights), sum(weights))

		def isPossible(capacity):
			days = 0
			temp = 0
			for w in weights:
				if temp + w <= capacity:
					temp += w
				else:
					days += 1
					temp = w
			return days + 1 <= D
		while l < r:
			mid = l + (r - l) // 2
			if isPossible(mid):
				r = mid
			else:
				l = mid + 1
		return l


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def possible(K):
			if K < max(weights):
				return False
			day = 1
			temp = K
			for we in weights:
				if temp < we:
					temp = K - we
					day += 1
				else:
					temp -= we
			return not day > D
		(lo, hi) = (max(weights), sum(weights))
		while lo < hi:
			mi = (lo + hi) // 2
			if not possible(mi):
				lo = mi + 1
			else:
				hi = mi
		return lo


class Solution:

	def shipWithinDays(self, weights: List[int], limit: int) -> int:

		def count_days(cap: int) -> int:
			cur_weight = 0
			days = 1
			for w in weights:
				if cur_weight + w > cap:
					days += 1
					cur_weight = w
				else:
					cur_weight += w
			return days
		left = max(weights)
		right = sum(weights)
		while left < right:
			mid = left + (right - left) // 2
			time = count_days(mid)
			if time > limit:
				left = mid + 1
			else:
				right = mid
		return left


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		(l, r) = (max(weights), sum(weights))

		def checkCapacity(maxCap):
			day = 1
			temp = 0
			for i in weights:
				temp += i
				if temp > maxCap:
					temp = i
					day += 1
				if day > D:
					return False
			return True
		while l < r:
			mid = l + (r - l) // 2
			if checkCapacity(mid):
				r = mid
			else:
				l = mid + 1
		return l


from collections import deque

class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def canShip(capacity):
			nonlocal D
			(count, loaded) = (1, 0)
			for w in weights:
				if loaded + w <= capacity:
					loaded += w
				else:
					count += 1
					loaded = w
			return count <= D
		max_weight = max(weights)
		(low, high) = (sum(weights) // D, max_weight * len(weights) // D + 1)
		while low < high:
			mid = low + (high - low) // 2
			if mid < max_weight or not canShip(mid):
				low = mid + 1
			else:
				high = mid
		return low


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		left = max(weights)
		right = sum(weights)
		res = right
		while left <= right:
			mid = left + (right - left) // 2
			d = self.get_day(weights, mid)
			if d <= D:
				res = min(res, mid)
				right = mid - 1
			else:
				left = mid + 1
		return res

	def get_day(self, weights, cap):
		cur = 0
		res = 0
		for x in weights:
			if cur + x > cap:
				res += 1
				cur = 0
			cur += x
		return res + 1


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def numberofDaysWithCapacity(weights, mid):
			(sum, c) = (0, 1)
			for i in range(len(weights)):
				sum += weights[i]
				if sum > mid:
					c += 1
					sum = weights[i]
			return c
		(left, right) = (max(weights), sum(weights))
		while left <= right:
			mid = left + (right - left) // 2
			daysRequired = numberofDaysWithCapacity(weights, mid)
			if daysRequired > D:
				left = mid + 1
			else:
				res = mid
				right = mid - 1
		return res


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def fun(t):
			s = 0
			d = 0
			for i in range(n):
				s = s + weights[i]
				if s > t:
					d = d + 1
					s = weights[i]
			return d
		n = len(weights)
		(lo, hi) = (max(weights), sum(weights))
		while lo <= hi:
			c = lo + (hi - lo) // 2
			if fun(c) < D:
				hi = c - 1
			else:
				lo = c + 1
		return lo


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		high = 0
		low = 0
		for weight in weights:
			high += weight
			low = max(low, weight)
		while low < high:
			mid = (high + low) // 2
			days = 1
			cur_weight = 0
			for weight in weights:
				if cur_weight + weight > mid:
					cur_weight = 0
					days += 1
				cur_weight += weight
			if days > D:
				low = mid + 1
			else:
				high = mid
		return low


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		mi = max(weights)
		ma = sum(weights)

		def canFit(cap):
			num = 1
			re = cap
			for i in range(len(weights)):
				x = weights[i]
				if x > re:
					re = cap
					num += 1
				re -= x
			return num <= D
		while mi < ma:
			mid = mi + (ma - mi) // 2
			if canFit(mid):
				ma = mid
			else:
				mi = mid + 1
		return mi


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def check(cap):
			(cnt, load) = (0, 0)
			for x in weights:
				if x > cap:
					return False
				if load + x < cap:
					load += x
				elif load + x == cap:
					(cnt, load) = (cnt + 1, 0)
				else:
					(cnt, load) = (cnt + 1, x)
			return cnt + (load > 0) <= D
		(l, r) = (1, sum(weights))
		while l < r:
			p = l + (r - l) // 2
			if not check(p):
				l = p + 1
			else:
				r = p
		return l


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		high = sum(weights)
		low = max(weights)

		def check(cap):
			cnt = 1
			summ = 0
			for w in weights:
				if summ + w <= cap:
					summ += w
				else:
					cnt += 1
					summ = w
				if cnt > D:
					return False
			return True
		while low != high:
			mid = (low + high) // 2
			if check(mid):
				high = mid
			else:
				low = mid + 1
		return low


class Solution:

	def shipWithinDays(self, weights, D):
		(l, r) = (max(weights), sum(weights))
		while l < r:
			(m, days, curWeight) = ((l + r) // 2, 1, 0)
			for weight in weights:
				if curWeight + weight > m:
					days += 1
					curWeight = 0
				if days > D:
					l = m + 1
					break
				curWeight += weight
			else:
				r = m
		return l


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def can(x):
			(res, sum) = (1, 0)
			for w in weights:
				if w > x:
					return False
				if sum + w > x:
					res += 1
					sum = w
				else:
					sum += w
			return res <= D
		(mx, sum) = (0, 0)
		for i in weights:
			(mx, sum) = (max(mx, i), sum + i)
		(lo, hi) = (mx, sum)
		while lo < hi:
			mi = (hi - lo) // 2 + lo
			if not can(mi):
				lo = mi + 1
			else:
				hi = mi
		return lo


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def condition(minWeight):
			dayCt = 1
			curWeight = 0
			for (i, w) in enumerate(weights):
				if curWeight + w <= minWeight:
					curWeight += w
				else:
					dayCt += 1
					curWeight = w
			return dayCt <= D
		l = max(weights)
		r = sum(weights)
		while l < r:
			m = l + (r - l) // 2
			if condition(m):
				r = m
			else:
				l = m + 1
		return l


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		lower = max(weights)
		upper = sum(weights)
		while abs(lower - upper) > 1:
			mid = (lower + upper) // 2
			if self.is_shipped(mid, weights, D):
				upper = mid
			else:
				lower = mid
		if lower == upper or self.is_shipped(lower, weights, D):
			return lower
		else:
			return upper

	def is_shipped(self, cap, weights, D):
		tmp = 0
		count = 1
		for i in range(len(weights)):
			tmp += weights[i]
			if tmp == cap:
				count += 1
				tmp = 0
			elif tmp > cap:
				count += 1
				tmp = weights[i]
		return count <= D


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		left = max(weights)
		right = sum(weights)
		retval = sum(weights)
		while left <= right:
			mid = left + (right - left) // 2
			(temp, count) = (0, 1)
			for i in range(len(weights)):
				temp += weights[i]
				if temp > mid:
					temp = weights[i]
					count += 1
				elif temp == mid:
					temp = 0
					count += 1
			if count > D:
				left = mid + 1
			else:
				retval = mid
				right = mid - 1
		return retval


class Solution:

	def isValidCapacity(self, weights, D, capacity):
		totalDays = 1
		i = 0
		runningSum = 0
		for i in range(len(weights)):
			if runningSum + weights[i] > capacity:
				runningSum = weights[i]
				totalDays += 1
			else:
				runningSum += weights[i]
		return totalDays <= D

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		low = max(weights)
		high = sum(weights)
		while low < high:
			mid = (low + high) // 2
			if self.isValidCapacity(weights, D, mid):
				high = mid
			else:
				low = mid + 1
		return low


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def can_ship(x):
			cnt = 1
			curr = 0
			for w in weights:
				if w > x:
					return False
				if curr + w > x:
					curr = w
					cnt += 1
				else:
					curr += w
				if cnt > D:
					return False
			return cnt <= D
		(left, right) = (1, sum(weights))
		while left < right:
			mid = (right - left) // 2 + left
			if can_ship(mid):
				right = mid
			else:
				left = mid + 1
		return left


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		left = max(weights)
		right = sum(weights)
		while left < right:
			mid = left + (right - left) // 2
			if self.condition(mid, weights) <= D:
				right = mid
			else:
				left = mid + 1
		return left

	def condition(self, k, weights):
		d = 0
		cur_weight = 0
		for weight in weights:
			if cur_weight + weight == k:
				d += 1
				cur_weight = 0
			elif cur_weight + weight > k:
				d += 1
				cur_weight = weight
			else:
				cur_weight += weight
		return d + 1 if cur_weight > 0 else d


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		total = sum(weights)
		maxW = max(weights)
		low = total // D
		high = low + maxW

		def isok(weights, D, cap):
			curr = cap
			count = 1
			for w in weights:
				if w > cap:
					return False
				if curr - w < 0:
					count += 1
					curr = cap - w
				else:
					curr -= w
			return count <= D
		while low != high:
			mid = (low + high) // 2
			if isok(weights, D, mid):
				high = mid
			else:
				low = mid + 1
		return low


class Solution:

	def numD(self, arr, n):
		count = 0
		ans = 0
		for i in range(len(arr)):
			count += arr[i]
			if count > n:
				ans += 1
				count = arr[i]
		return ans + 1

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		l = -1
		r = 25000000
		for i in range(len(weights)):
			if weights[i] > l:
				l = weights[i]
		while l <= r:
			mid = (l + r) // 2
			if self.numD(weights, mid) <= D:
				r = mid - 1
			elif self.numD(weights, mid) > D:
				l = mid + 1
		return l


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		l = max(weights)
		r = sum(weights)
		length = len(weights)
		while l <= r:
			mid = l + (r - l) // 2
			cur = 0
			toD = 1
			for i in range(length):
				if cur + weights[i] > mid:
					toD += 1
					cur = 0
				cur += weights[i]
			if toD > D:
				l = mid + 1
			else:
				r = mid - 1
		return l


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		lo = max(weights)
		hi = sum(weights)
		n = len(weights)
		while lo < hi:
			guess = lo + (hi - lo) // 2
			guessDays = 1
			currLoad = 0
			for i in range(n):
				if currLoad + weights[i] > guess:
					currLoad = 0
					guessDays += 1
				currLoad += weights[i]
			if guessDays <= D:
				hi = guess
			else:
				lo = guess + 1
		return lo


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:

		def __can(capacity):
			days = 0
			partial_sum = 0
			for i in range(len(weights)):
				if partial_sum + weights[i] > capacity:
					partial_sum = 0
					days += 1
				partial_sum += weights[i]
			days += 1
			return days <= D
		(lo, hi) = (max(weights), sum(weights))
		while lo + 1 < hi:
			mid = (lo + hi) // 2
			if __can(mid) == True:
				hi = mid
			else:
				lo = mid
		return lo if __can(lo) == True else hi


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		(l, h) = (max(weights), sum(weights))
		total = h
		while l <= h:
			m = (l + h) // 2
			(days, count, t) = (D, 0, 0)
			for w in weights:
				if days == 0:
					break
				if count + w > m:
					count = w
					days -= 1
				else:
					count += w
				t += w
			if t == total and days > 0:
				h = m - 1
			else:
				l = m + 1
		return l


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		(l, r) = (max(weights), sum(weights))
		while l + 1 < r:
			mid = (l + r) // 2
			if self.calculateNumberOfDays(weights, mid) > D:
				l = mid
			else:
				r = mid
		if self.calculateNumberOfDays(weights, l) <= D:
			return l
		else:
			return r

	def calculateNumberOfDays(self, weights, K):
		num_of_days = 0
		_sum = 0
		for i in range(len(weights)):
			if _sum + weights[i] > K:
				num_of_days += 1
				_sum = weights[i]
			else:
				_sum += weights[i]
		if _sum:
			num_of_days += 1
		return num_of_days


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		left = 0
		right = 0
		for i in range(len(weights)):
			left = max(weights[i], left)
			right += weights[i]
		while left < right:
			mid = (left + right) // 2
			if self.greedy_match(mid, weights, D):
				right = mid
			else:
				left = mid + 1
		return left

	def greedy_match(self, boat_weight, weights, days):
		cur_days = 1
		cur_weight = 0
		for i in range(len(weights)):
			if cur_weight + weights[i] > boat_weight:
				cur_weight = 0
				cur_days += 1
				if cur_days > days:
					return False
			cur_weight += weights[i]
		return True


class Solution:

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		weights_sum = sum(weights)

		def necessary_days(capacity):
			days = 0
			ws = 0
			for w in weights:
				if ws + w <= capacity:
					ws += w
				else:
					days += 1
					ws = w
			return days + 1
		low = max(weights)
		high = weights_sum
		capacity_guess = (low + high) // 2
		while low <= high:
			d = necessary_days(capacity_guess)
			if d <= D:
				high = capacity_guess - 1
			else:
				low = capacity_guess + 1
			capacity_guess = (low + high) // 2
		return low


class Solution:

	def check(self, weights, limit):
		cur = 0
		count = 1
		for i in range(len(weights)):
			if cur + weights[i] > limit:
				count += 1
				cur = weights[i]
			else:
				cur += weights[i]
		return count

	def shipWithinDays(self, weights: List[int], D: int) -> int:
		l = max(weights)
		r = sum(weights)
		ans = 1
		while l <= r:
			mid = int((r + l) / 2)
			if self.check(weights, mid) <= D:
				ans = mid
				r = mid - 1
			else:
				l = mid + 1
		return ans