Cod sursa(job #3303772)

Utilizator dansiminaSimina Dan Marius dansimina Data 17 iulie 2025 19:53:28
Problema Elimin Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;

ifstream fin ("elimin.in");
ofstream fout("elimin.out");

int main()
{
    unsigned int n, m, r, c;
    unsigned int maxSum = 0;
    fin >> n >> m >> r >> c;
    vector<vector<unsigned int>> mat;
    if(n <= m)
    {
        mat = vector<vector<unsigned int>>(n + 9, vector<unsigned int>(m + 9));
        for(unsigned int i = 1; i <= n; i++)
        {
            for(unsigned int j = 1; j <= m; j++)
                fin >> mat[i][j];
        }
    }
    else
    {
        mat = vector<vector<unsigned int>>(m + 9, vector<unsigned int>(n + 9));
        vector<vector<unsigned int>> reverse(n + 9, vector<unsigned int>(m + 9));
        for(unsigned int i = 1; i <= n; i++)
        {
            for(unsigned int j = 1; j <= m; j++)
                fin >> reverse[i][j];
        }

        for(unsigned int i = 1; i <= m; i++)
        {
            for(unsigned int j = 1; j <= n; j++)
                mat[i][j] = reverse[j][i];
        }

        swap(n, m);
        swap(r, c);
    }

    if(n <= m)
    {
        for(unsigned int i = 0; i < (1 << n); i++)
        {
            if(__builtin_popcount(i) == r)
            {
                vector modified = mat;
                for(unsigned int j = 0; j < n; j++)
                    if(i & (1 << j))
                    {
                        for(unsigned int j1 = 1; j1 <= m; j1++)
                            modified[j + 1][j1] = 0;
                    }
                vector<pair<unsigned int ,unsigned int>> sumCol(m);
                for(unsigned int j1 = 1; j1 <= m; j1++)
                {
                    for(unsigned int i1 = 1; i1 <= n; i1++)
                    {
                        sumCol[j1 - 1].first += modified[i1][j1];
                    }
                    sumCol[j1 - 1].second = j1;
                }

                sort(sumCol.begin(), sumCol.end());
                for(unsigned int i = 0; i < c; i++)
                {
                    for(unsigned int i1 = 1; i1 <= n; i1++)
                        modified[i1][sumCol[i].second] = 0;
                }

                unsigned int sum = 0;
                for(unsigned int i1 = 1; i1 <= n; i1++)
                {
                    for(unsigned int j1 = 1; j1 <= m; j1++)
                        sum += modified[i1][j1];
                }

                maxSum = max(sum, maxSum);
            }
        }
    }

    fout << maxSum;

    return 0;
}