Theft at World Bank | C ++ program for the above approach ; Custom comparator ; Function to find the maximum profit ; Stores the pairs of elements of B and A at the same index ; Iterate over the range [ 0 , N ] ; If current integer is perfect square ; Push the pair of B [ i ] and A [ i ] in vector V ; Sorts the vector using the custom comparator ; Stores the maximum profit ; Traverse the vector V ; If V [ i ] . second is less than W ; Increment profit by V [ i ] . first ; Decrement V [ i ] . second from W ; Otherwise ; Update profit ; Return the value of profit ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool comp ( pair < long long , long long > p1 , pair < long long , long long > p2 ) { long double a = p1 . first , b = p1 . second ; long double c = p2 . first , d = p2 . second ; long double val1 = 0 , val2 = 0 ; val1 = a / b ; val2 = c / d ; return val1 > val2 ; } long double maximumProfit ( int A [ ] , int B [ ] , int N , long long W ) { vector < pair < long long , long long > > V ; for ( int i = 0 ; i < N ; i ++ ) { long long temp = sqrt ( A [ i ] ) ; if ( temp * temp == A [ i ] ) continue ; V . push_back ( { B [ i ] , A [ i ] } ) ; } sort ( V . begin ( ) , V . end ( ) , comp ) ; long double profit = 0.00 ; for ( int i = 0 ; i < V . size ( ) ; i ++ ) { if ( V [ i ] . second <= W ) { profit += V [ i ] . first ; W -= V [ i ] . second ; } else { profit += V [ i ] . first * ( ( long double ) W / V [ i ] . second ) ; break ; } } return profit ; } int main ( ) { int N = 3 ; long long W = 10 ; int A [ ] = { 4 , 5 , 7 } ; int B [ ] = { 8 , 5 , 4 } ; cout << maximumProfit ( A , B , N , W ) << endl ; return 0 ; }