Cod sursa(job #596511)

Utilizator darrenRares Buhai darren Data 17 iunie 2011 15:58:47
Problema Elimin Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <cstring>
#include <fstream>
#include <algorithm>

using namespace std;

int N, M, R, C;
int A[16][8000];
int S[8000], result;

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

    fin >> N >> M >> R >> C;

    if (N <= M)
        for (int i = 1; i <= N; ++i)
            for (int j = 1; j <= M; ++j)
                fin >> A[i][j];
    else
    {
        for (int i = 1; i <= N; ++i)
            for (int j = 1; j <= M; ++j)
                fin >> A[j][i];
        swap(N, M);
        swap(R, C);
    }

    for (int i = 0; i < (1 << N); ++i)
    {
        int nrb = 0, aux = i;
        while (aux) ++nrb, aux &= aux - 1;

        if (nrb != R) continue;

        memset(S, 0, sizeof(S));

        int nows = 0;
        for (int k = 1; k <= M; ++k)
            for (int j = 1; j <= N; ++j)
                if (!(i & (1 << (j - 1))))
                {
                    S[k] += A[j][k];
                    nows += A[j][k];
                }

        sort(S + 1, S + M + 1);
        for (int j = 1; j <= C; ++j)
            nows -= S[j];

        result = max(result, nows);
    }

    fout << result;

    fin.close();
    fout.close();
}