<p>You have <code>k</code> bags. You are given a <strong>0-indexed</strong> integer array <code>weights</code> where <code>weights[i]</code> is the weight of the <code>i<sup>th</sup></code> marble. You are also given the integer <code>k.</code></p>

<p>Divide the marbles into the <code>k</code> bags according to the following rules:</p>

<ul>
	<li>No bag is empty.</li>
	<li>If the <code>i<sup>th</sup></code> marble and <code>j<sup>th</sup></code> marble are in a bag, then all marbles with an index between the <code>i<sup>th</sup></code> and <code>j<sup>th</sup></code> indices should also be in that same bag.</li>
	<li>If a bag consists of all the marbles with an index from <code>i</code> to <code>j</code> inclusively, then the cost of the bag is <code>weights[i] + weights[j]</code>.</li>
</ul>

<p>The <strong>score</strong> after distributing the marbles is the sum of the costs of all the <code>k</code> bags.</p>

<p>Return <em>the <strong>difference</strong> between the <strong>maximum</strong> and <strong>minimum</strong> scores among marble distributions</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> weights = [1,3,5,1], k = 2
<strong>Output:</strong> 4
<strong>Explanation:</strong> 
The distribution [1],[3,5,1] results in the minimal score of (1+1) + (3+1) = 6. 
The distribution [1,3],[5,1], results in the maximal score of (1+3) + (5+1) = 10. 
Thus, we return their difference 10 - 6 = 4.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> weights = [1, 3], k = 2
<strong>Output:</strong> 0
<strong>Explanation:</strong> The only distribution possible is [1],[3]. 
Since both the maximal and minimal score are the same, we return 0.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k &lt;= weights.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= weights[i] &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    def putMarbles(self, weights: List[int], k: int) -> int:
        # solution redone here, original solutions further below
        n = len(weights)
        heap_arr = []
        for i in range(n - 1):
            cost = weights[i] + weights[i + 1]
            heapq.heappush(heap_arr, -cost)
            while len(heap_arr) > k - 1:
                heapq.heappop(heap_arr)
        res_min = weights[0] + weights[n - 1] - sum(heap_arr)
        
        heap_arr = []
        for i in range(n - 1):
            cost = weights[i] + weights[i + 1]
            heapq.heappush(heap_arr, cost)
            while len(heap_arr) > k - 1:
                heapq.heappop(heap_arr)
        res_max = weights[0] + weights[n - 1] + sum(heap_arr)

        return res_max - res_min















































        # """Solution 1:"""
        # if k == 1:
        #     return 0
        # n = len(weights)
        # # there are n - 1 possible splitting points
        # # k buckets means k - 1 splitting points

        # # for max score, we want to pick the k - 1 largest splitting points
        # max_split_points = []
        # for i in range(n - 1):
        #     x = weights[i] + weights[i + 1]
        #     if len(max_split_points) < k - 1:
        #         heapq.heappush(max_split_points, x)
        #     else:
        #         smallest = heapq.heappop(max_split_points)
        #         heapq.heappush(max_split_points, max(smallest, x))
        # max_score = weights[0] + weights[n - 1] + sum(max_split_points)

        # # for min score, we want to pick the k - 1 smallest splitting points
        # min_split_points = []
        # for i in range(n - 1):
        #     x = weights[i] + weights[i + 1]
        #     if len(min_split_points) < k - 1:
        #         heapq.heappush(min_split_points, -x)
        #     else:
        #         largest_magnitude = -heapq.heappop(min_split_points)
        #         heapq.heappush(min_split_points, -min(largest_magnitude, x))
        # min_score = weights[0] + weights[n - 1] + (-1 * sum(min_split_points))

        # return max_score - min_score
        
        # """Solution 2:"""
        # # n = len(weights)
        # # # there are n-1 possible splitting points
        # # pair_sums = [weights[i] + weights[i + 1] for i in range(n - 1)]
        # # pair_sums.sort()

        # # # k buckets means k - 1 splitting points

        # # # for max score, we want to pick the k - 1 largest splitting points
        # # max_score = weights[0] + weights[n - 1]
        # # for i in range(k - 1):
        # #     max_score += pair_sums[n - 2 - i]
        
        # # # for min score, we want to pick the k - 1 smallest splitting points
        # # min_score = weights[0] + weights[n - 1]
        # # for i in range(k - 1):
        # #     min_score += pair_sums[i]

        # # return max_score - min_score
672