In this HackerEarth Monk And Champions League problem solution 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.


HackerEarth Monk And Champions League problem solution


HackerEarth Monk And Champions League problem solution.

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long int
#define pb push_back
#define mk make_pair
ll power(ll a, ll b) {
ll x = 1, y = a;
    while(b > 0) {
        if(b%2 == 1) {
            x=(x*y);
            if(x>mod) x%=mod;
        }
        y = (y*y);
        if(y>mod) y%=mod;
        b /= 2;
    }
    return x;
}
int main()
{
    int n,m,i;
    ll s;
    s = 0;
    cin>>m>>n;
    int a[m];
    priority_queue<int> q;
    for(i = 0; i < m; i++) {
        cin>>a[i];
        q.push(a[i]);
    }
    for(i = 0; i < n; i++) {
        int x = q.top();
        s += x;
        q.pop();
        x--;
        if(x) q.push(x);
    }
    cout<<s<<endl;
    return 0;
}

Second solution

#include <bits/stdc++.h>
using namespace std;
#define PII pair <int, int>
priority_queue <int> seats; 
map <int, int> x; 
int main()
{
    ios_base::sync_with_stdio(0); 
    int N, M; cin >> N >> M;
    assert (1<=N and N<=1000000); 
    assert (1<=M and M<=1000000); 
    for (int g=1; g<=N; g++){
        int a; cin >> a;
        seats.push(a); 
        assert (1<=a and a<=1000000); 
        x[a]++; 
    } 
    long long ans = 0; 
    for (int g=0; g<M; g++){
        int x = seats.top(); ans+=x; seats.pop();seats.push(x-1); 
    }
    cout <<ans;
    return 0;
}