Smart Shopkeeper

Problem Statement

Smart Shopkeeper A smart shopkeeper bought n items, and the cost price of item i is a[i] ( 0 <= i < n ). He now wants to sell all n items and earn the maximum total profit, under one rule: exactly k of the items may be sold with a profit of at most 20% of their cost price, and the remaining n - k items may be sold with a profit of at most 10% of their cost price. The shopkeeper chooses which items go into the 20% group. The profit of an item is its selling price minus its cost price, so an item with cost c earns at most c / 5 in the 20% group and at most c / 10 in the 10% group. Every cost price is a multiple of 10 , so both amounts are whole numbers. Find the maximum total profit. Implement the function solve(a, k) , which returns that maximum profit. Input Format The first line contains an integer n , the total number of items. Each of the next n lines contains an integer a[i] , the cost price of item i . The last line contains an integer k , the number of items that may be sol