monk-and-champions-league

Monk's favourite game is Football and his favourite club is "Manchester United". Manchester United has qualified for the Champions League Final which is to be held at the Wembley Stadium in London. So, he decided to go there and watch his favourite team play. After reaching the stadium, he saw that many people have lined up for the match tickets. He knows that there are M rows in the stadium with different seating capacities. They may or may not be equal. The price of the ticket depends on the row. If the row has K(always greater than 0) vacant seats, then the price of the ticket will be K pounds(units of British Currency). Now, every football fan standing in the line will get a ticket one by one.
Given the seating capacities of different rows, find the maximum possible pounds that the club will gain with the help of the ticket sales.

Input:
The first line consists of M and N. M denotes the number of seating rows in the stadium and N denotes the number of football fans waiting in the line to get a ticket for the match.
Next line consists of M space separated integers X[1],X[2],X[3].... X[M] where X[i] denotes the number of empty seats initially in the i^th row.  

Output:
Print in a single line the maximum pounds the club will gain.  

Constraints:
1 ≤ M ≤ 1000000
1 ≤ N ≤ 1000000
1 ≤ X[i] ≤ 1000000
Sum of X[i] for all 1 ≤ i ≤ M will always be greater than N.

SAMPLE INPUT
3 4
1 2 4

SAMPLE OUTPUT
11

Explanation

In the sample test case, number of rows is 3 and the 4 people waiting in line to get a ticket.
Since the maximum cost of ticket initially is 4 pounds, therefore the first person in line will buy a ticket for the 3rd row.
The person standing in line will again choose the 3rd row as it has the maximum number of seats, which will cost him 3 pounds.
The next person will have 2 choices, he can either choose the 2nd row or the 3rd row which will cost him 2 pounds.
Similarly, the last person will choose the row will 2 seats remaining, which will cost him 2 pounds.  
Total cost = 4+3+2+2 = 11 pounds.

Source: hackerearth | Difficulty: EASY
Tags: Data structures


Solutions:
import heapq
m,n=list(map(int,input().split()))
a=[-int(x) for x in input().split()]
heapq.heapify(a)
s=0
for i in range(n):
	t=heapq.heappop(a)
	s+=-t
	t+=1
	if t<0:
		heapq.heappush(a,t)
print(s)


import heapq

def solve(n, xs):
	xs = [-x for x in xs]
	heapq.heapify(xs)
	tot = 0
	for _ in range(n):
		price = xs[0]
		tot += price
		heapq.heapreplace(xs, price + 1)
	return -tot

if __name__ == '__main__':
	_, n = list(map(int, input().split()))
	xs = list(map(int, input().split()))
	print(solve(n, xs))


q=input().split()
M=int(q[0])
N=int(q[1])
l=input().split()
A=[0]*(len(l)+1)
for i in range(1,len(l)+1):
	A[i]=int(l[i-1])
count=0
	
	
def max_heapify(a,i,m1):
	left=2*i
	right=left+1
	if left<=m1 and a[left]>a[i]:
		largest=left
	else:
		largest=i
	if right<=m1 and a[right]>a[largest]:
		largest=right
	if largest!=i:
		max=a[largest]
		a[largest]=a[i]
		a[i]=max
		max_heapify(a,largest,m1)
def build_maxheap(b):
	i=M/2
	while i>=1:
		max_heapify(b,i,M)
		i-=1
	return b
	
A=build_maxheap(A)
while N>0:
	count+=A[1]
	A[1]-=1
	max_heapify(A,1,M)
	N-=1
print(count)
	



import heapq

values=[int(x) for x in input().split()]


res=[-int(x) for x in input().split()]

heapq.heapify(res)


tot=0
for i in range(0,values[1]):
	val=heapq.heappop(res)
	tot=tot-val
	heapq.heappush(res,val+1)

print(tot)


class PriorityQueue:

	def __init__(self,L=[0]):
		
		self.queue  = L
		self.length = len(L)-1
		if len(L)>1:
			self.build_heap()

	def build_heap(self):
		N = self.length
		for i in range(N/2,0,-1):
			self.heapify(i,N)
 

	def heapify(self,ind,N):
		arr   = self.queue
		left  = 2*ind       #left child
		right = 2*ind + 1   #right child

		if left <= N and arr[left] > arr[ind]:
			largest = left
		else:
			largest = ind

		if right <= N and arr[right] > arr[largest]:
			largest = right

		if (largest != ind):
		
			arr[ind],arr[largest]   = arr[largest],arr[ind]  # swap both
			
			self.heapify(largest,N)

	def front(self):
		return self.queue[1]

	def dequeue(self):
		arr = self.queue 
		if self.length==0:
			return None
		N = self.length
		result = arr[1]
	   
		arr[1]  = arr[N]
		self.length -=1
		arr.pop()
		self.heapify(1,self.length)
		return result
		
		

	def increase_key(self,ind,value):
		arr = self.queue
	   
		if (value < arr[ind]):
			return None

		arr[ind][1] = value
												 
		while (ind > 1 and arr[ind]> arr[ind/2]):
	   
			arr[ind],arr[ind/2] = arr[ind/2],arr[ind]
			ind = ind/2

	def insert(self,value):
		arr           = self.queue
		length        = self.length
		length        += 1
		self.length   +=1

		arr.append(value)
		
		ind = length
		while (ind > 1 and arr[ind]> arr[ind/2]):
		
			arr[ind],arr[ind/2]   = arr[ind/2],arr[ind]
			ind = ind/2

	def pprint(self):
		print(self.queue[1:self.length+1])





M,N = [int(x) for x in input().split()]
row = [int(x) for x in input().split()]

p_row = [0]

p_row+=row

q = PriorityQueue(p_row)

total = 0
for i in range(N):
	val   = q.dequeue()
	total+=val
	q.insert(val-1)
print(total)
	





import heapq

num_rows, fans = list(map(int, input().strip().split(" ")))
rows_spaces = [-int(x) for x in input().strip().split(" ")]
heapq.heapify(rows_spaces)
sum_sales = 0
for fan in range(fans):
	current_max = heapq.heappop(rows_spaces)
	sum_sales += current_max
	current_max += 1
	heapq.heappush(rows_spaces, current_max)
print(-sum_sales)