HackerEarth Monsters in Grid problem solution

In this HackerEarth Monsters in Grid problem solution You are given a grid of size NxM, where some of the cells have monsters in them. You have N+M lasers, one at each row and one at each column. You can fire any laser at most once. Assume that these lasers move in a straight line without being blocked by anything. Each monster has a health of 2. In one laser strike, a monster’s health is reduced by 1. If the monster’s health becomes 0, it dies. You have to find the maximum number of monsters that can be killed if you can fire at most K lasers.

HackerEarth Monsters in Grid problem solution.

#include <bits/stdc++.h>
using namespace std;
#define ll  long long int
#define MOD 1000000007
ll pow_mod(ll a, ll b, ll mod) {
    ll res = 1;
    while(b) {
        if(b & 1) {
            res = (res * a) % mod;
        }
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}
int ar[25][25];
int main() {
    int n, m, k;
    cin >> n >> m >> k;
    assert(1 <= n && n <= 20);
    assert(1 <= m && m <= 20);
    assert(1 <= k && k <= n + m);
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            cin >> ar[i][j];
        }
    }
    int res = 0;
    for(int i = 0; i < (1 << m); ++i) {
        int lft = k - __builtin_popcount(i);
        if(lft < 0) {
            continue;
        }
        vector < int > kill;
        for(int a = 0; a < n; ++a) {
            int c = 0;
            for(int b = 0; b < m; ++b) {
                if((i >> b) & 1) {
                    if(ar[a][b] == 1) {
                        c += 1;
                    }
                }
            }
            kill.push_back(c);
        }
        sort(kill.begin(), kill.end());
        reverse(kill.begin(), kill.end());
        int s = 0;
        lft = min(lft, n);
        for(int i = 0; i < lft; ++i) {
            s += kill[i];
        }
        res = max(res, s);
    }
    cout << res << endl;
    return 0;
}

Second solution

#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>

#include <memory.h>
#include <assert.h>

#define y0 sdkfaslhagaklsldk

#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd
#define have adsgagshdshfhds

#define eps 1e-6
#define M_PI 3.141592653589793
#define bs 1000000007
#define bsize 350

using namespace std;

const int INF = 1e9;
const int N = 1600000;

int n, m, k, ar[200][200];
int C[200];
int ans;

int main(){
    ios_base::sync_with_stdio(0);
    //cin.tie(0);

    assert(cin >> n >> m);
    assert(cin >> k);

    assert(n >= 1 && n <= 20 && m >= 1 && m <= 20 && k >= 1 && k <= n + m);

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            assert(cin >> ar[i][j]);
            assert(ar[i][j] >= 0 && ar[i][j] <= 1);
        }
    }

    for (int mask = 0; mask < (1 << n); mask++)
    {
        int used = 0;
        for (int i = 0; i < n; i++)
        {
            if (mask&(1 << i))
                used++;
        }

        if (used>k)
            continue;

        for (int i = 0; i < m; i++)
        {
            C[i] = 0;
        }

        for (int i = 0; i < n; i++)
        {
            if (mask&(1 << i))
            for (int j = 0; j < m; j++)
            {

                if (ar[i][j])
                    C[j]++;

            }
        }

        vector<int> v;
        for (int i = 0; i < m; i++)
        {
            v.push_back(C[i]);
        }
        sort(v.begin(), v.end());
        reverse(v.begin(), v.end());
        int here = 0;
        for (int i = 0; i < v.size(); i++)
        {
            if (used >= k)
                break;
            used++;
            here += v[i];
        }

        ans = max(ans, here);
    }

    cout << ans << endl;

    cin.get(); cin.get();
    return 0;
}

coding problems solutions