Cod sursa(job #2451063)

Utilizator uvIanisUrsu Ianis Vlad uvIanis Data 25 august 2019 15:35:13
Problema Elimin Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.63 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;

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

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

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

    if(N > M)
    {
        swap(N, M);
        swap(R, C);
        for(ursu i = 1; i <= N; i++) for(ursu j = i + 1; j <= M; j++) swap(matrix[i][j], matrix[j][i]);
    }

    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) break;
        }

        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);

        }
    }

    if(C==0 && R==0)
    {
        for(ursu i = 1; i <= N; i++) for(ursu j = 1; j <= M; j++) s_max += matrix[i][j];
    }

    fout << s_max;
}