Maximum Possible Rating of a Coding Contest | C ++ program to find the Maximum Possible Rating of a Coding Contest ; Function to sort all problems descending to upvotes ; Function to return maximum rating ; Declaring vector of pairs ; Each pair represents a problem with its points and upvotes ; Step ( 1 ) - Sort problems by their upvotes value in decreasing order ; Declaring min_heap or priority queue to track of the problem with minimum points . ; Step ( 2 ) - Loop for i = 0 to K - 1 and do accordingly ; Step ( 3 ) - Loop for i = K to N - 1 and do accordingly ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool Comparator ( pair < int , int > p1 , pair < int , int > p2 ) { return p1 . second > p2 . second ; } int FindMaxRating ( int N , int Point [ ] , int Upvote [ ] , int K ) { vector < pair < int , int > > vec ; for ( int i = 0 ; i < N ; i ++ ) { vec . push_back ( make_pair ( Point [ i ] , Upvote [ i ] ) ) ; } sort ( vec . begin ( ) , vec . end ( ) , Comparator ) ; priority_queue < int , vector < int > , greater < int > > pq ; int total_points = 0 , max_rating = 0 ; for ( int i = 0 ; i < K ; i ++ ) { total_points = total_points + vec [ i ] . first ; max_rating = max ( max_rating , total_points * vec [ i ] . second ) ; pq . push ( vec [ i ] . first ) ; } for ( int i = K ; i < N ; i ++ ) { if ( pq . top ( ) < vec [ i ] . first ) { total_points = total_points - pq . top ( ) + vec [ i ] . first ; max_rating = max ( max_rating , total_points * vec [ i ] . second ) ; pq . pop ( ) ; pq . push ( vec [ i ] . first ) ; } } return max_rating ; } int main ( ) { int Point [ ] = { 2 , 10 , 3 , 1 , 5 , 8 } ; int Upvote [ ] = { 5 , 4 , 3 , 9 , 7 , 2 } ; int N = sizeof ( Point ) / sizeof ( Point [ 0 ] ) ; int K = 2 ; cout << " Maximum ▁ Rating ▁ of ▁ Coding ▁ Contest ▁ is : ▁ " << FindMaxRating ( N , Point , Upvote , K ) ; return 0 ; }