Cod sursa(job #2451054)

Utilizator uvIanisUrsu Ianis Vlad uvIanis Data 25 august 2019 15:00:43
Problema Elimin Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.06 kb
#include <bits/stdc++.h>
using namespace std;

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

typedef unsigned short ursu;
ursu N, M, R, C;

size_t s_max{0};

vector<vector<ursu>> matrix;
vector<ursu> cols, lines;

int main()
{
    fin >> N >> M >> R >> C;

    matrix.resize(N + 1, vector<ursu>(M + 1));
    cols.resize(M + 1);
    lines.resize(N + 1);

    for(ursu i = 1; i <= N; i++) for(ursu j = 1; j <= M; j++) fin >> matrix[i][j];

    for(long long i = 1; i < (1 << N); i++)
    {
        ursu contor{0};
        for(ursu j = 0; j < N; j++) if(i & (1 << j)) contor++;

        if(contor == R)
        {
            for(ursu c = 1; c <= M; c++)
            {
                cols[c] = 0;
                for(ursu l = 1; l <= N; l++) cols[c] += matrix[l][c];
            }


            for(ursu j = 0; j < N; j++)
            {
                if(i & (1 << j))
                {
                    for(ursu c = 1; c <= M; c++) cols[c] -= matrix[j + 1][c];
                }
            }

            sort(cols.begin() + 1, cols.end());

            size_t s_current{0};

            for(ursu c = C + 1; c <= M; c++) s_current += cols[c];

            s_max = max(s_max, s_current);

        }
    }


    for(long long i = 1; i < (1 << M); i++)
    {
        ursu contor{0};
        for(ursu j = 0; j < M; j++) if(i & (1 << j)) contor++;

        if(contor == C)
        {
            for(ursu c = 1; c <= N; c++)
            {
                lines[c] = 0;
                for(ursu l = 1; l <= M; l++) lines[c] += matrix[c][l];
            }


            for(ursu j = 0; j < M; j++)
            {
                if(i & (1 << j))
                {
                    for(ursu c = 1; c <= M; c++) lines[c] -= matrix[c][j + 1];
                }
            }

            sort(lines.begin() + 1, lines.end());

            size_t s_current{0};

            for(ursu c = R + 1; c <= N; c++) s_current += lines[c];

            s_max = max(s_max, s_current);

        }
    }

    fout << s_max;
}