3462. Maximum Sum With at Most K Elements

You are given a 2D integer matrix grid of size n x m, an integer array limits of length n, and an integer k. The task is to find the maximum sum of at most k elements from the matrix grid such that:

• The number of elements taken from the ith row of grid does not exceed limits[i].

Return the maximum sum.

c++

class Solution {
public:
    long long maxSum(vector<vector<int>>& grid, vector<int>& limits, int k) {
        vector<long long> S;
        for(int i = 0; i < grid.size(); i++) {
            while(limits[i]--) {
                int best = 0;
                for(int j = 1; j < grid[i].size(); j++) {
                    if(grid[i][j] >= grid[i][best]) best = j;
                }
                swap(grid[i].back(), grid[i][best]);
                S.push_back(grid[i].back());
                grid[i].pop_back();
            }
        }
        partial_sort(S.begin(), S.begin() + k, S.end(), greater<int>());
        return accumulate(begin(S), begin(S) + k, 0ll);
    }
};