Maximum possible Array sum after performing given operations | C ++ implementation to find the maximum possible sum of array after performing given operations ; Function to get maximum sum after q operations ; priority queue to get maximum sum ; Push pair , value and 1 in the priority queue ; Push pair , value ( to be replaced ) and number of elements ( to be replaced ) ; Add top n elements from the priority queue to get max sum ; pr is the pair pr . first is the value and pr . second is the occurrence ; pop from the priority queue ; Add value to answer ; Update n ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void max_sum ( int ar [ ] , int n , int q , int x [ ] , int y [ ] ) { int ans = 0 , i ; priority_queue < pair < int , int > > pq ; for ( i = 0 ; i < n ; i ++ ) pq . push ( { ar [ i ] , 1 } ) ; for ( i = 0 ; i < q ; i ++ ) pq . push ( { y [ i ] , x [ i ] } ) ; while ( n > 0 ) { auto pr = pq . top ( ) ; pq . pop ( ) ; ans += pr . first * min ( n , pr . second ) ; n -= pr . second ; } cout << ans << " STRNEWLINE " ; } int main ( ) { int ar [ ] = { 200 , 100 , 200 , 300 } ; int n = ( sizeof ar ) / ( sizeof ar [ 0 ] ) ; int q = 2 ; int x [ ] = { 2 , 3 } ; int y [ ] = { 100 , 90 } ; max_sum ( ar , n , q , x , y ) ; return 0 ; }